시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10 8 6 100.000%

문제

7로 나누었을 때, 나머지가 1 또는 6인 숫자를 7N+{1,6} 숫자라고 한다. 하지만, 발음하기 어려우므로 이러한 숫자를 월요일-토요일 숫자라고 하자.

월요일-토요일 숫자 a와 b가 있을 때, ax = b를 만족하는 월요일-토요일 숫자 x가 있다면, a를 b의 월요일-토요일 약수라고 한다. 사실, 월요일-토요일 숫자 a가 b의 약수(일반적인 약수)라면, a는 b의 월요일-토요일 약수이다. 또, 역도 성립한다.

월요일-토요일 소수란 1보다 큰 월요일-토요일 숫자가 1과 자기 자신을 제외하고 월요일-토요일 약수가 없는 수이다. 월요일-토요일 숫자가 소수일 때, 이 수는 월요일-토요일 소수이다. 하지만, 그 역은 성립하지 않는다. 예를 들어, 27은 월요일-토요일 소수이지만, 소수는 아니다.

어떤 월요일-토요일 숫자의 월요일-토요일 약수 중에서 월요일-토요일 소수인 것을 월요일-토요일 소인수라고 한다. 예를 들어, 27은 216의 월요일-토요일 소인수이다. (216 = 27 * 8)

1보다 큰 월요일-토요일 솟자는 하나 또는 그 이상의 월요일-토요일 소수의 곱으로 나타낼 수 있다. 이러한 표현은 유일하지 않다. 예를 들어, 216 = 6 * 6 * 6 = 8 * 27이다.

월요일-토요일 숫자가 주어졌을 때, 월요일-토요일 소인수를 모두 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 월요일-토요일 수가 주어진다. 이 수는 1보다 크고, 300000보다 작다. 입력의 마지막 줄에는 1이 주어진다.

출력

입력으로 주어진 월요일-토요일 숫자에 대해서, 그 숫자를 출력하고, ":"을 출력한 다음에 월요일-토요일 소인수를 오름차순으로 출력한다. 모든 월요일-토요일 소인수 앞에는 공백을 한 칸 출력해야 한다.

예제 입력 1

205920
262144
262200
279936
299998
1

예제 출력 1

205920: 6 8 13 15 20 22 55 99
262144: 8
262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185
279936: 6 8 27
299998: 299998

힌트

W3sicHJvYmxlbV9pZCI6IjQ5NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQ3XHViODVjIFx1YjA5OFx1YjIwNFx1YzVjOFx1Yzc0NCBcdWI1NGMsIFx1YjA5OFx1YmEzOFx1YzljMFx1YWMwMCAxIFx1YjYxMFx1YjI5NCA2XHVjNzc4IFx1YzIyYlx1Yzc5MFx1Yjk3YyA3Tit7MSw2fSBcdWMyMmJcdWM3OTBcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmMxY1x1Yzc0Y1x1ZDU1OFx1YWUzMCBcdWM1YjRcdWI4MjRcdWM2YjBcdWJiYzBcdWI4NWMgXHVjNzc0XHViN2VjXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzIyYlx1Yzc5MFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjMjJiXHVjNzkwIGFcdWM2NDAgYlx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBheCA9IGJcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjMjJiXHVjNzkwIHhcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0LCBhXHViOTdjIGJcdWM3NTggXHVjNmQ0XHVjNjk0XHVjNzdjLVx1ZDFhMFx1YzY5NFx1Yzc3YyBcdWM1N2RcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYWNcdWMyZTQsIFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjMjJiXHVjNzkwIGFcdWFjMDAgYlx1Yzc1OCBcdWM1N2RcdWMyMTgoXHVjNzdjXHViYzE4XHVjODAxXHVjNzc4IFx1YzU3ZFx1YzIxOClcdWI3N2NcdWJhNzQsIGFcdWIyOTQgYlx1Yzc1OCBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzU3ZFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWM1ZWRcdWIzYzQgXHVjMTMxXHViOWJkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzE4Y1x1YzIxOFx1Yjc4MCAxXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzIyYlx1Yzc5MFx1YWMwMCAxXHVhY2ZjIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwIFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjNTdkXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzE4Y1x1YzIxOFx1Yzc3YyBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWIyOTQgXHVjNmQ0XHVjNjk0XHVjNzdjLVx1ZDFhMFx1YzY5NFx1Yzc3YyBcdWMxOGNcdWMyMThcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhZGY4IFx1YzVlZFx1Yzc0MCBcdWMxMzFcdWI5YmRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyN1x1Yzc0MCBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzE4Y1x1YzIxOFx1Yzc3NFx1YzljMFx1YjljYywgXHVjMThjXHVjMjE4XHViMjk0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNWI0XHViNWE0IFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjNTdkXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzE4Y1x1YzIxOFx1Yzc3OCBcdWFjODNcdWM3NDQgXHVjNmQ0XHVjNjk0XHVjNzdjLVx1ZDFhMFx1YzY5NFx1Yzc3YyBcdWMxOGNcdWM3NzhcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyN1x1Yzc0MCAyMTZcdWM3NTggXHVjNmQ0XHVjNjk0XHVjNzdjLVx1ZDFhMFx1YzY5NFx1Yzc3YyBcdWMxOGNcdWM3NzhcdWMyMThcdWM3NzRcdWIyZTQuICgyMTYgPSAyNyAqIDgpPFwvcD5cclxuXHJcbjxwPlxyXG5cdDFcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjMTlmXHVjNzkwXHViMjk0IFx1ZDU1OFx1YjA5OCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ0NWNcdWQ2MDRcdWM3NDAgXHVjNzIwXHVjNzdjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMjE2ID0gNiAqIDYgKiA2ID0gOCAqIDI3XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzE4Y1x1Yzc3OFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjNmQ0XHVjNjk0XHVjNzdjLVx1ZDFhMFx1YzY5NFx1Yzc3YyBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwLCAzMDAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzZkNFx1YzY5NFx1Yzc3Yy1cdWQxYTBcdWM2OTRcdWM3N2MgXHVjMjJiXHVjNzkwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZGY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsICZxdW90OzomcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjIFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWM2ZDRcdWM2OTRcdWM3N2MtXHVkMWEwXHVjNjk0XHVjNzdjIFx1YzE4Y1x1Yzc3OFx1YzIxOFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNmQ0XHVjNjk0XHVjNzdjLVx1ZDFhMFx1YzY5NFx1Yzc3YyBcdWMxOGNcdWM3NzhcdWMyMTggXHVjNTVlXHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWQ1NWMgXHVjZTc4IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDk2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1vbmRheS1TYXR1cmRheSBQcmltZSBGYWN0b3JzIiwiZGVzY3JpcHRpb24iOiI8cD5DaGllZiBKdWRnZSYjMzk7cyBsb2csIHN0YXJkYXRlIDQ4NjQyLjUuIFdlIGhhdmUgZGVjaWRlZCB0byBtYWtlIGEgcHJvYmxlbSBmcm9tIGVsZW1lbnRhcnkgbnVtYmVyIHRoZW9yeS4gVGhlIHByb2JsZW0gbG9va3MgbGlrZSBmaW5kaW5nIGFsbCBwcmltZSBmYWN0b3JzIG9mIGEgcG9zaXRpdmUgaW50ZWdlciwgYnV0IGl0IGlzIG5vdC48XC9wPlxyXG5cclxuPHA+QSBwb3NpdGl2ZSBpbnRlZ2VyIHdob3NlIHJlbWFpbmRlciBkaXZpZGVkIGJ5IDcgaXMgZWl0aGVyIDEgb3IgNiBpcyBjYWxsZWQgYSA3Tit7MSw2fSBudW1iZXIuIEJ1dCBhcyBpdCBpcyBoYXJkIHRvIHByb25vdW5jZSwgd2Ugc2hhbGwgY2FsbCBpdCBhIE1vbmRheS1TYXR1cmRheSBudW1iZXIuPFwvcD5cclxuXHJcbjxwPkZvciBNb25kYXktU2F0dXJkYXkgbnVtYmVycyBhIGFuZCBiLCB3ZSBzYXkgYSBpcyBhIE1vbmRheS1TYXR1cmRheSBkaXZpc29yIG9mIGIgaWYgdGhlcmUgZXhpc3RzIGEgTW9uZGF5LVNhdHVyZGF5IG51bWJlciB4IHN1Y2ggdGhhdCBheCA9IGIuIEl0IGlzIGVhc3kgdG8gc2hvdyB0aGF0IGZvciBhbnkgTW9uZGF5LVNhdHVyZGF5IG51bWJlcnMgYSBhbmQgYiwgaXQgaG9sZHMgdGhhdCBhIGlzIGEgTW9uZGF5LVNhdHVyZGF5IGRpdmlzb3Igb2YgYiBpZiBhbmQgb25seSBpZiBhIGlzIGEgZGl2aXNvciBvZiBiIGluIHRoZSB1c3VhbCBzZW5zZS48XC9wPlxyXG5cclxuPHA+V2UgY2FsbCBhIE1vbmRheS1TYXR1cmRheSBudW1iZXIgYSBNb25kYXktU2F0dXJkYXkgcHJpbWUgaWYgaXQgaXMgZ3JlYXRlciB0aGFuIDEgYW5kIGhhcyBubyBNb25kYXktU2F0dXJkYXkgZGl2aXNvcnMgb3RoZXIgdGhhbiBpdHNlbGYgYW5kIDEuIEEgTW9uZGF5LVNhdHVyZGF5IG51bWJlciB3aGljaCBpcyBhIHByaW1lIGluIHRoZSB1c3VhbCBzZW5zZSBpcyBhIE1vbmRheS1TYXR1cmRheSBwcmltZSBidXQgdGhlIGNvbnZlcnNlIGRvZXMgbm90IGFsd2F5cyBob2xkLiBGb3IgZXhhbXBsZSwgMjcgaXMgYSBNb25kYXktU2F0dXJkYXkgcHJpbWUgYWx0aG91Z2ggaXQgaXMgbm90IGEgcHJpbWUgaW4gdGhlIHVzdWFsIHNlbnNlLiBXZSBjYWxsIGEgTW9uZGF5LVNhdHVyZGF5IHByaW1lIHdoaWNoIGlzIGEgTW9uZGF5LVNhdHVyZGF5IGRpdmlzb3Igb2YgYSBNb25kYXktU2F0dXJkYXkgbnVtYmVyIGEgYSBNb25kYXktU2F0dXJkYXkgcHJpbWUgZmFjdG9yIG9mIGEuIEZvciBleGFtcGxlLCAyNyBpcyBvbmUgb2YgdGhlIE1vbmRheS1TYXR1cmRheSBwcmltZSBmYWN0b3JzIG9mIDIxNiwgc2luY2UgMjcgaXMgYSBNb25kYXktU2F0dXJkYXkgcHJpbWUgYW5kIDIxNiA9IDI3ICZ0aW1lczsgOCBob2xkcy48XC9wPlxyXG5cclxuPHA+QW55IE1vbmRheS1TYXR1cmRheSBudW1iZXIgZ3JlYXRlciB0aGFuIDEgY2FuIGJlIGV4cHJlc3NlZCBhcyBhIHByb2R1Y3Qgb2Ygb25lIG9yIG1vcmUgTW9uZGF5LVNhdHVyZGF5IHByaW1lcy4gVGhlIGV4cHJlc3Npb24gaXMgbm90IGFsd2F5cyB1bmlxdWUgZXZlbiBpZiBkaWZmZXJlbmNlcyBpbiBvcmRlciBhcmUgaWdub3JlZC4gRm9yIGV4YW1wbGUsIDIxNiA9IDYgJnRpbWVzOyA2ICZ0aW1lczsgNiA9IDggJnRpbWVzOyAyNyBob2xkcy48XC9wPlxyXG5cclxuPHA+T3VyIGNvbnRlc3RhbnRzIHNob3VsZCB3cml0ZSBhIHByb2dyYW0gdGhhdCBvdXRwdXRzIGFsbCBNb25kYXktU2F0dXJkYXkgcHJpbWUgZmFjdG9ycyBvZiBlYWNoIGlucHV0IE1vbmRheS1TYXR1cmRheSBudW1iZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBsaW5lcyBlYWNoIG9mIHdoaWNoIGNvbnRhaW5zIGEgc2luZ2xlIE1vbmRheS1TYXR1cmRheSBudW1iZXIuIEVhY2ggTW9uZGF5LVNhdHVyZGF5IG51bWJlciBpcyBncmVhdGVyIHRoYW4gMSBhbmQgbGVzcyB0aGFuIDMwMDAwMCAodGhyZWUgaHVuZHJlZCB0aG91c2FuZCkuIFRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBkaWdpdCAxLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IE1vbmRheS1TYXR1cmRheSBudW1iZXIsIGl0IHNob3VsZCBiZSBwcmludGVkLCBmb2xsb3dlZCBieSBhIGNvbG9uIGA6JiMzOTsgYW5kIHRoZSBsaXN0IG9mIGl0cyBNb25kYXktU2F0dXJkYXkgcHJpbWUgZmFjdG9ycyBvbiBhIHNpbmdsZSBsaW5lLiBNb25kYXktU2F0dXJkYXkgcHJpbWUgZmFjdG9ycyBzaG91bGQgYmUgbGlzdGVkIGluIGFzY2VuZGluZyBvcmRlciBhbmQgZWFjaCBzaG91bGQgYmUgcHJlY2VkZWQgYnkgYSBzcGFjZS4gQWxsIHRoZSBNb25kYXktU2F0dXJkYXkgcHJpbWUgZmFjdG9ycyBzaG91bGQgYmUgcHJpbnRlZCBvbmx5IG9uY2UgZXZlbiBpZiB0aGV5IGRpdmlkZSB0aGUgaW5wdXQgTW9uZGF5LVNhdHVyZGF5IG51bWJlciBtb3JlIHRoYW4gb25jZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=