시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 14 12 100.000%

문제

모든 자연수 N은 (2a)(3b)의 합으로 나타낼 수 있다. 이 때, 서로 약수/배수 관계인 두 항이 있어서는 안 된다.

  • 1 = (20)(30)
  • 7 = (22)(30) + (20)(31)
  • 31 = (24)(30) + (20)(32) + (21)(31) = (22)(30) + (20)(33)

N이 주어졌을 때, 이를 (2a)(3b)의 합으로 나타내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 정수 N이 주어진다. (1 <= N < 231)

출력

각 테스트 케이스에 대해 첫째 줄에는 항의 개수 M을 출력한다. 그다음 M개의 줄에 걸쳐 합을 구성하는 항을 출력한다. 어떤 항이 (2a)(3b)일때, a b를 공백으로 구분하여 출력하면 된다.

예제 입력 1

6
1
7
31
7776
531441
123456789

예제 출력 1

1
0 0
2
2 0
0 1
3
4 0
0 2
1 1
1
5 5
1
0 12
8
3 13
4 12
2 15
7 8
9 6
0 16
10 5
15 2
W3sicHJvYmxlbV9pZCI6IjI3MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIyLDMgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxXHVjNzU4IFx1ZDU2OSIsImRlc2NyaXB0aW9uIjoiPHA+XHViYWE4XHViNGUwIFx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzQwICgyPHN1cD5hPFwvc3VwPikoMzxzdXA+YjxcL3N1cD4pXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjMTFjXHViODVjIFx1YzU3ZFx1YzIxOFwvXHViYzMwXHVjMjE4IFx1YWQwMFx1YWNjNFx1Yzc3OCBcdWI0NTAgXHVkNTZkXHVjNzc0IFx1Yzc4OFx1YzViNFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgPSAoMjxzdXA+MDxcL3N1cD4pKDM8c3VwPjA8XC9zdXA+KTxcL2xpPlxyXG5cdDxsaT43ID0gKDI8c3VwPjI8XC9zdXA+KSgzPHN1cD4wPFwvc3VwPikgKyAoMjxzdXA+MDxcL3N1cD4pKDM8c3VwPjE8XC9zdXA+KTxcL2xpPlxyXG5cdDxsaT4zMSA9ICgyPHN1cD40PFwvc3VwPikoMzxzdXA+MDxcL3N1cD4pICsgKDI8c3VwPjA8XC9zdXA+KSgzPHN1cD4yPFwvc3VwPikgKyAoMjxzdXA+MTxcL3N1cD4pKDM8c3VwPjE8XC9zdXA+KSA9ICgyPHN1cD4yPFwvc3VwPikoMzxzdXA+MDxcL3N1cD4pICsgKDI8c3VwPjA8XC9zdXA+KSgzPHN1cD4zPFwvc3VwPik8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5OXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NFx1Yjk3YyAoMjxzdXA+YTxcL3N1cD4pKDM8c3VwPmI8XC9zdXA+KVx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSZsdDs9VCZsdDs9MSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0Oz0gTiAmbHQ7IDI8c3VwPjMxPFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NmRcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjhcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHVkNTZkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViNWE0IFx1ZDU2ZFx1Yzc3NCAoMjxzdXA+YTxcL3N1cD4pKDM8c3VwPmI8XC9zdXA+KVx1Yzc3Y1x1YjU0YywgYSBiXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzI3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTm9uLWRpdmlzaWJsZSAyLTMgUG93ZXIgU3VtcyIsImRlc2NyaXB0aW9uIjoiPHA+RXZlcnkgcG9zaXRpdmUgaW50ZWdlciBOIGNhbiBiZSB3cml0dGVuIGluIGF0IGxlYXN0IG9uZSB3YXkgYXMgYSBzdW0gb2YgdGVybXMgb2YgdGhlIGZvcm0gKDI8c3VwPmE8XC9zdXA+KSgzPHN1cD5iPFwvc3VwPikgd2hlcmUgbm8gdGVybSBpbiB0aGUgc3VtIGV4YWN0bHkgZGl2aWRlcyBhbnkgb3RoZXIgdGVybSBpbiB0aGUgc3VtLiBGb3IgZXhhbXBsZTombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xID0gKDI8c3VwPjA8XC9zdXA+KSgzPHN1cD4wPFwvc3VwPik8XC9saT5cclxuXHQ8bGk+NyA9ICgyPHN1cD4yPFwvc3VwPikoMzxzdXA+MDxcL3N1cD4pICsgKDI8c3VwPjA8XC9zdXA+KSgzPHN1cD4xPFwvc3VwPik8XC9saT5cclxuXHQ8bGk+MzEgPSAoMjxzdXA+NDxcL3N1cD4pKDM8c3VwPjA8XC9zdXA+KSArICgyPHN1cD4wPFwvc3VwPikoMzxzdXA+MjxcL3N1cD4pICsgKDI8c3VwPjE8XC9zdXA+KSgzPHN1cD4xPFwvc3VwPikgPSAoMjxzdXA+MjxcL3N1cD4pKDM8c3VwPjA8XC9zdXA+KSArICgyPHN1cD4wPFwvc3VwPikoMzxzdXA+MzxcL3N1cD4pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm90ZSBmcm9tIHRoZSBleGFtcGxlIG9mIDMxIHRoYXQgdGhlIHJlcHJlc2VudGF0aW9uIGlzIG5vdCB1bmlxdWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB0YWtlcyBhcyBpbnB1dCBhIHBvc2l0aXZlIGludGVnZXIgTiBhbmQgb3V0cHV0cyBhIHJlcHJlc2VudGF0aW9uIG9mIE4gYXMgYSBzdW0gb2YgdGVybXMgb2YgdGhlIGZvcm0gKDI8c3VwPmE8XC9zdXA+KSgzPHN1cD5iPFwvc3VwPikuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIEMsICgxICZsZTsgQyAmbGU7IDEwMDApIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YXNldHMgdGhhdCBmb2xsb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggZGF0YXNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIG9mIGlucHV0IGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBOLCAoMSAmbGU7IE4gJmx0OyAyPHN1cD4zMTxcL3N1cD4pLCB3aGljaCBpcyB0aGUgbnVtYmVyIHRvIGJlIHJlcHJlc2VudGVkIGFzIGEgc3VtIG9mIHRlcm1zIG9mIHRoZSBmb3JtICgyPHN1cD5hPFwvc3VwPikoMzxzdXA+YjxcL3N1cD4pLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIHRoZSBvdXRwdXQgd2lsbCBiZSBhIHNpbmdsZSBsaW5lIGNvbnNpc3Rpbmcgb2Y6IFRoZSBkYXRhc2V0IG51bWJlciwgYSBzaW5nbGUgc3BhY2UsIHRoZSBudW1iZXIgb2YgdGVybXMgaW4geW91ciBzdW0gYXMgYSBkZWNpbWFsIGludGVnZXIgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UgZm9sbG93ZWQgYnkgcmVwcmVzZW50YXRpb25zIG9mIHRoZSB0ZXJtcyBpbiB0aGUgZm9ybSBbJmx0OzIgZXhwb25lbnQmZ3Q7LCZsdDszIGV4cG9uZW50Jmd0O10gd2l0aCB0ZXJtcyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuICZsdDsyIGV4cG9uZW50Jmd0OyBpcyB0aGUgcG93ZXIgb2YgMiBpbiB0aGUgdGVybSBhbmQgJmx0OzMgZXhwb25lbnQmZ3Q7IGlzIHRoZSBwb3dlciBvZiAzIGluIHRoZSB0ZXJtLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2006 Greater New York Programming Contest H번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: doju