시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5173 2210 1772 43.927%

문제

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+XHVhY2U4XHViNGRjXHViYzE0XHVkNzUwXHVjNzU4IFx1Y2Q5NFx1Y2UyMVx1Yzc0MCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjODE1XHVjMjE4XHViODYwXHVjNzU4IFx1YmJmOFx1ZDU3NFx1YWNiMCBcdWJiMzhcdWM4MWNcdWI4NWMsIDJcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YmFhOFx1YjRlMCBcdWM5ZGRcdWMyMThcdWIyOTQgXHViNDUwIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YWNlOFx1YjRkY1x1YmMxNFx1ZDc1MCBcdWMyMmJcdWM3OTBcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzlkZFx1YzIxOFx1Yjk3YyBcdWI0NTAgXHVjMThjXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNDVjXHVkNjA0XHVjNzQ0IFx1YWRmOCBcdWMyMmJcdWM3OTBcdWM3NTggXHVhY2U4XHViNGRjXHViYzE0XHVkNzUwIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIDQgPSAyICsgMiwgNiA9IDMgKyAzLCA4ID0gMyArIDUsIDEwID0gNSArIDUsIDEyID0gNSArIDcsIDE0ID0gMyArIDExLCAxNCA9IDcgKyA3XHVjNzc0XHViMmU0LiAxMDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHViYWE4XHViNGUwIFx1YzlkZFx1YzIxOCBuXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWFjZThcdWI0ZGNcdWJjMTRcdWQ3NTAgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Mlx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjOWRkXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1Yzc1OCBcdWFjZThcdWI0ZGNcdWJjMTRcdWQ3NTAgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI5Y2NcdWM1N2QgXHVhYzAwXHViMmE1XHVkNTVjIG5cdWM3NTggXHVhY2U4XHViNGRjXHViYzE0XHVkNzUwIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjQ1MCBcdWMxOGNcdWMyMThcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCBcdWM5ZGRcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICg0ICZsZTsgbiAmbGU7IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IG5cdWM3NTggXHVhY2U4XHViNGRjXHViYzE0XHVkNzUwIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWMxOGNcdWMyMThcdWIyOTQgXHVjNzkxXHVjNzQwIFx1YWM4M1x1YmQ4MFx1ZDEzMCBcdWJhM2NcdWM4MDAgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkwMjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHb2xkYmFjaFx1MjAxOXMgQ29uamVjdHVyZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBuYXR1cmFsIG51bWJlciBpcyBjYWxsZWQgYSBwcmltZSBudW1iZXIgKG9yIGEgcHJpbWUpIGlmIGl0IGlzIGJpZ2dlciB0aGFuIDEgYW5kIGhhcyBubyBkaXZpc29ycyBvdGhlciB0aGFuIDEgYW5kIGl0c2VsZi4gRm9yIGV4YW1wbGUsIDUgaXMgcHJpbWUsIHNpbmNlIG5vIG51bWJlciBleGNlcHQgMSBhbmQgNSBkaXZpZGVzIGl0LiBPbiB0aGUgb3RoZXIgaGFuZCwgNiBpcyBub3QgYSBwcmltZSBzaW5jZSA2ID0gMiAmdGltZXM7IDMgLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Hb2xkYmFjaCYjMzk7cyBjb25qZWN0dXJlIGlzIG9uZSBvZiB0aGUgZmFtb3VzIHVuc29sdmVkIHByb2JsZW1zIGluIG51bWJlciB0aGVvcnkgYW5kIGluIGFsbCBvZiBtYXRoZW1hdGljcy4gSXQgc3RhdGVzOiBFdmVyeSBldmVuIGludGVnZXIgZ3JlYXRlciB0aGFuIDIgY2FuIGJlIGV4cHJlc3NlZCBhcyB0aGUgc3VtIG9mIHR3byBwcmltZXMuIFN1Y2ggYSBudW1iZXIgaXMgY2FsbGVkIGEgR29sZGJhY2ggbnVtYmVyLiBFeHByZXNzaW5nIGEgZ2l2ZW4gZXZlbiBudW1iZXIgYXMgYSBzdW0gb2YgdHdvIHByaW1lcyBpcyBjYWxsZWQgYSBHb2xkYmFjaCBwYXJ0aXRpb24gb2YgdGhlIG51bWJlci4gRm9yIGV4YW1wbGUsIDQgPSAyICsgMiAsIDYgPSAzICsgMyAsIDggPSAzICsgNSAsIDEwID0gNyArIDMgb3IgMTAgPSA1ICsgNSAsIDEyID0gNSArIDcgLCAxNCA9IDMgKyAxMSBvciAxNCA9IDcgKyA3IC4gTm90ZSB0aGF0IEdvbGRiYWNoIHBhcnRpdGlvbiBoYXMgYmVlbiBmb3VuZCBmb3IgYW55IGV2ZW4gaW50ZXJnZXIgbiBsZXNzIHRoYW4gMTAwMDAuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGFueSBldmVuIGludGVnZXIgbiBncmVhdGVyIHRoYW4gMiwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgcHJpbnRzIHRoZSB0d28gcHJpbWVzIG9mIHRoZSBHb2xkYmFjaCBwYXJ0aXRpb24gb2YgbiAuIElmIHRoZXJlIGFyZSBtb3JlIHRoYW4gb25lIEdvbGRiYWNoIHBhcnRpdGlvbnMgb2YgbiwgZmluZCBhIHBhcnRpdGlvbiBzdWNoIHRoYXQgdGhlIGRpZmZlcmVuY2Ugb2YgdGhlIHR3byBwcmltZXMgb2YgaXQgaXMgbWluaW1pemVkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhbiBldmVuIGludGVnZXIgbiAoNCAmbGU7IG4gJmxlOyAxMCwwMDAgKSAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gRm9yIGVhY2ggdGVzdCBjYXNlLCBmaW5kIHRoZSBHb2xkYmFjaCBwYXJ0aXRpb24gYXMgZGVzY3JpYmVkIGFib3ZlLCBhbmQgcHJpbnQgaXRzIHR3byBwcmltZXMgaW4gbm9uLWRlY3JlYXNpbmcgb3JkZXIgd2l0aCBvbmUgYmxhbmsgYmV0d2VlbiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==