시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 7229 3285 2479 46.070%

문제

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 숫자를 골드바흐 숫자라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 숫자의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다. (4 ≤ n ≤ 10,000)

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

예제 입력 1

3
8
10
16

예제 출력 1

3 5
5 5
5 11
W3sicHJvYmxlbV9pZCI6IjkwMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZThcdWI0ZGNcdWJjMTRcdWQ3NTBcdWM3NTggXHVjZDk0XHVjZTIxIiwiZGVzY3JpcHRpb24iOiI8cD4xXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWM3OTBcdWM1ZjBcdWMyMTgmbmJzcDtcdWM5MTFcdWM1ZDBcdWMxMWMgJm5ic3A7MVx1YWNmYyBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWM1N2RcdWMyMThcdWFjMDAgXHVjNWM2XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjk3YyBcdWMxOGNcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA1XHViMjk0IDFcdWFjZmMgNVx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHVjNTdkXHVjMjE4XHVhYzAwIFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMThjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIDZcdWM3NDAgNiA9IDIgJnRpbWVzOyAzIFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMThjXHVjMjE4XHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2U4XHViNGRjXHViYzE0XHVkNzUwXHVjNzU4IFx1Y2Q5NFx1Y2UyMVx1Yzc0MCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjODE1XHVjMjE4XHViODYwXHVjNzU4IFx1YmJmOFx1ZDU3NFx1YWNiMCBcdWJiMzhcdWM4MWNcdWI4NWMsIDJcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YmFhOFx1YjRlMCBcdWM5ZGRcdWMyMThcdWIyOTQgXHViNDUwIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YWNlOFx1YjRkY1x1YmMxNFx1ZDc1MCBcdWMyMmJcdWM3OTBcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzlkZFx1YzIxOFx1Yjk3YyBcdWI0NTAgXHVjMThjXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNDVjXHVkNjA0XHVjNzQ0IFx1YWRmOCBcdWMyMmJcdWM3OTBcdWM3NTggXHVhY2U4XHViNGRjXHViYzE0XHVkNzUwIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIDQgPSAyICsgMiwgNiA9IDMgKyAzLCA4ID0gMyArIDUsIDEwID0gNSArIDUsIDEyID0gNSArIDcsIDE0ID0gMyArIDExLCAxNCA9IDcgKyA3XHVjNzc0XHViMmU0LiAxMDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwJm5ic3A7XHViYWE4XHViNGUwIFx1YzlkZFx1YzIxOCBuXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWFjZThcdWI0ZGNcdWJjMTRcdWQ3NTAgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Mlx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjOWRkXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1Yzc1OCBcdWFjZThcdWI0ZGNcdWJjMTRcdWQ3NTAgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI5Y2NcdWM1N2QgXHVhYzAwXHViMmE1XHVkNTVjIG5cdWM3NTggXHVhY2U4XHViNGRjXHViYzE0XHVkNzUwIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjMThjXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAgXHVjOWRkXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoNCAmbGU7IG4gJmxlOyAxMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBuXHVjNzU4IFx1YWNlOFx1YjRkY1x1YmMxNFx1ZDc1MCBcdWQzMGNcdWQyZjBcdWMxNThcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMThjXHVjMjE4XHViMjk0IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWJkODBcdWQxMzAgXHViYTNjXHVjODAwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MDIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR29sZGJhY2hcdTIwMTlzIENvbmplY3R1cmUiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbmF0dXJhbCBudW1iZXIgaXMgY2FsbGVkIGEgcHJpbWUgbnVtYmVyIChvciBhIHByaW1lKSBpZiBpdCBpcyBiaWdnZXIgdGhhbiAxIGFuZCBoYXMgbm8gZGl2aXNvcnMgb3RoZXIgdGhhbiAxIGFuZCBpdHNlbGYuIEZvciBleGFtcGxlLCA1IGlzIHByaW1lLCBzaW5jZSBubyBudW1iZXIgZXhjZXB0IDEgYW5kIDUgZGl2aWRlcyBpdC4gT24gdGhlIG90aGVyIGhhbmQsIDYgaXMgbm90IGEgcHJpbWUgc2luY2UgNiA9IDIgJnRpbWVzOyAzIC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R29sZGJhY2gmIzM5O3MgY29uamVjdHVyZSBpcyBvbmUgb2YgdGhlIGZhbW91cyB1bnNvbHZlZCBwcm9ibGVtcyBpbiBudW1iZXIgdGhlb3J5IGFuZCBpbiBhbGwgb2YgbWF0aGVtYXRpY3MuIEl0IHN0YXRlczogRXZlcnkgZXZlbiBpbnRlZ2VyIGdyZWF0ZXIgdGhhbiAyIGNhbiBiZSBleHByZXNzZWQgYXMgdGhlIHN1bSBvZiB0d28gcHJpbWVzLiBTdWNoIGEgbnVtYmVyIGlzIGNhbGxlZCBhIEdvbGRiYWNoIG51bWJlci4gRXhwcmVzc2luZyBhIGdpdmVuIGV2ZW4gbnVtYmVyIGFzIGEgc3VtIG9mIHR3byBwcmltZXMgaXMgY2FsbGVkIGEgR29sZGJhY2ggcGFydGl0aW9uIG9mIHRoZSBudW1iZXIuIEZvciBleGFtcGxlLCA0ID0gMiArIDIgLCA2ID0gMyArIDMgLCA4ID0gMyArIDUgLCAxMCA9IDcgKyAzIG9yIDEwID0gNSArIDUgLCAxMiA9IDUgKyA3ICwgMTQgPSAzICsgMTEgb3IgMTQgPSA3ICsgNyAuIE5vdGUgdGhhdCBHb2xkYmFjaCBwYXJ0aXRpb24gaGFzIGJlZW4gZm91bmQgZm9yIGFueSBldmVuIGludGVyZ2VyIG4gbGVzcyB0aGFuIDEwMDAwLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhbnkgZXZlbiBpbnRlZ2VyIG4gZ3JlYXRlciB0aGFuIDIsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHByaW50cyB0aGUgdHdvIHByaW1lcyBvZiB0aGUgR29sZGJhY2ggcGFydGl0aW9uIG9mIG4gLiBJZiB0aGVyZSBhcmUgbW9yZSB0aGFuIG9uZSBHb2xkYmFjaCBwYXJ0aXRpb25zIG9mIG4sIGZpbmQgYSBwYXJ0aXRpb24gc3VjaCB0aGF0IHRoZSBkaWZmZXJlbmNlIG9mIHRoZSB0d28gcHJpbWVzIG9mIGl0IGlzIG1pbmltaXplZC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYW4gZXZlbiBpbnRlZ2VyIG4gKDQgJmxlOyBuICZsZTsgMTAsMDAwICkgLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIEZvciBlYWNoIHRlc3QgY2FzZSwgZmluZCB0aGUgR29sZGJhY2ggcGFydGl0aW9uIGFzIGRlc2NyaWJlZCBhYm92ZSwgYW5kIHByaW50IGl0cyB0d28gcHJpbWVzIGluIG5vbi1kZWNyZWFzaW5nIG9yZGVyIHdpdGggb25lIGJsYW5rIGJldHdlZW4gdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=