시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1260 672 576 57.948%

문제

정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다.

'5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 수도 있다.'

예를 들면,

  • 7 = 2 + 2 + 3
  • 11 = 2 + 2 + 7
  • 25 = 7 + 7 + 11

5보다 큰 임의의 홀수를 입력받아서, 그 홀수가 어떻게 세 소수의 합으로 표현될 수 있는지 (또는 불가능한지) 알아보는 프로그램을 작성하시오.

입력

첫째 줄에 T(Test Case의 수를 의미함)가 주어진다.

입력은 T개의 Test Case로 이루어진다.

각 Test Case는 하나의 정수 K (7 ≤ K < 1,000, K는 홀수)로 구성된다.

출력

T줄에 걸쳐서, 각 줄에 K가 어떻게 세 소수의 합으로 표현되는지 출력해야 한다.

가능하다면 그 세 소수를 오름차순 정렬하여 출력하면 된다.

여러 개의 답이 가능하다면 그 중 하나만 출력하면 되고, 만약 불가능하다면 0을 출력한다.

예제 입력 1

3
7
11
25

예제 출력 1

2 2 3
2 2 7
5 7 13

힌트

W3sicHJvYmxlbV9pZCI6IjExNTAyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWMxOGNcdWMyMTggXHViYjM4XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMThcdWI4NjAoXHVjMjE4XHVkNTU5KVx1YzVkMFx1YzExYywgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWMxOGNcdWMyMTggXHViYjM4XHVjODFjKDMtcHJpbWVzIHByb2JsZW0pIFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Y2Q5NFx1Y2UyMVx1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiYjMzk7NVx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjNzg0XHVjNzU4XHVjNzU4IFx1ZDY0MFx1YzIxOFx1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWMxOGNcdWMyMThcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJiM2NcdWI4NjAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzE4Y1x1YzIxOFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YjM1NFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiYjMzk7PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+NyA9IDIgKyAyICsgMzxcL2xpPlxyXG5cdDxsaT4xMSA9IDIgKyAyICsgNzxcL2xpPlxyXG5cdDxsaT4yNSA9IDcgKyA3ICsgMTE8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD41XHViY2Y0XHViMmU0IFx1ZDA3MCBcdWM3ODRcdWM3NThcdWM3NTggXHVkNjQwXHVjMjE4XHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YzU0NFx1YzExYywgXHVhZGY4IFx1ZDY0MFx1YzIxOFx1YWMwMCZuYnNwO1x1YzViNFx1YjViYlx1YWM4YyBcdWMxMzggXHVjMThjXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCAoXHViNjEwXHViMjk0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1Y1x1YzljMCkgXHVjNTRjXHVjNTQ0XHViY2Y0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFQoVGVzdCBDYXNlXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NjgpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzQwIFRcdWFjMWNcdWM3NTggVGVzdCBDYXNlXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFRlc3QgQ2FzZVx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4IEsgKDcgJmxlOyBLICZsdDsgMSwwMDAsIEtcdWIyOTQgXHVkNjQwXHVjMjE4KVx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMsIFx1YWMwMSBcdWM5MDRcdWM1ZDAgS1x1YWMwMCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjMTM4IFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBcdWFkZjggXHVjMTM4IFx1YzE4Y1x1YzIxOFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWMgXHVjODE1XHViODJjXHVkNTU4XHVjNWVjJm5ic3A7XHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIyZjVcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0IFx1YWRmOCBcdWM5MTEmbmJzcDtcdWQ1NThcdWIwOThcdWI5Y2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxOFx1YWNlMCwmbmJzcDtcdWI5Y2NcdWM1N2QgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNTAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiMy1QcmltZXMgUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gbnVtYmVyIHRoZW9yeSwgdGhlIDMtcHJpbWVzIHByb2JsZW0gc3RhdGVzIHRoYXQ6PFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPlxyXG48cD5FdmVyeSBvZGQgbnVtYmVyIGdyZWF0ZXIgdGhhbiA1IGNhbiBiZSBleHByZXNzZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSBwcmltZXMuIChBIHByaW1lIG1heSBiZSB1c2VkIG1vcmUgdGhhbiBvbmNlIGluIHRoZSBzYW1lIHN1bS4pPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlNvbWUgZXhhbXBsZXMgb2YgdGhlIHByb2JsZW0gYXJlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjcgPSAyICsgMiArIDM8XC9saT5cclxuXHQ8bGk+MTEgPSAyICsgMiArIDc8XC9saT5cclxuXHQ8bGk+MjUgPSA3ICsgNyArIDExPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gMTkzOSwgUnVzc2lhbiBtYXRoZW1hdGljaWFuIEkuIE0uIFZpbm9ncmFkb3Ygc2hvd2VkIHRoYXQgYW55IHN1ZiBpY2llbnRseSBsYXJnZSBvZGQgaW50ZWdlciBjYW4gYmUgZXhwcmVzc2libGUgYXMgYSBzdW0gb2YgdGhyZWUgcHJpbWVzLiBMYXRlciBpdCBpcyBzaG93biB0aGF0IHN1ZmZpY2llbnRseSBsYXJnZSBpbiBWaW5vZ3JhZG92JnJzcXVvO3MgcHJvb2YgbWVhbnQgbnVtYmVycyBncmVhdGVyIHRoYW4gMzxzdXA+MzxzdXA+MTU8XC9zdXA+PFwvc3VwPiAmYXN5bXA7IDEwPHN1cD43MDAwMDAwPFwvc3VwPi4gVGhlIGJlc3Qga25vd24gaW1wcm92ZWQgYm91bmQgZm9yIHRoZSBmaWd1cmUgaXMgYXBwcm94aW1hdGVseSBlPHN1cD4zMTAwPFwvc3VwPiAmYXN5bXA7IDIgJnRpbWVzOyAxMDxzdXA+MTM0NjxcL3N1cD4uIFRoaXMgbnVtYmVyIGlzIHRvbyBsYXJnZSB0byBhZG1pdCBjaGVja2luZyBhbGwgc21hbGxlciBudW1iZXJzIGJ5IGNvbXB1dGVyLiBHaXZlbiBhIHBvc2l0aXZlIG9kZCBpbnRlZ2VyIGdyZWF0ZXIgdGhhbiA1LCB3cml0ZSBhIHByb2dyYW0gdG8gdGVzdCB3aGV0aGVyIG9yIG5vdCB0aGUgaW50ZWdlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSBwcmltZXMsIHdoZXJlIHRoZSBwcmltZXMgbWF5IG5vdCBiZSBkaXN0aW5jdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgYSBwb3NpdGl2ZSBpbnRlZ2VyIEsgKDcgJmxlOyBLICZsdDsgMSwwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBQcmludCB0aHJlZSBwcmltZXMsIGluIG5vbmRlY3JlYXNpbmcgb3JkZXIsIGlmIHRoZSBpbnB1dCBudW1iZXIgSyBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzdW0gb2YgZXhhY3RseSB0aHJlZSBwcmltZXMsIG90aGVyd2lzZSBwcmludCAwKHplcm8pLiBJZiB0aGVyZSBhcmUgbW9yZSB0aGFuIG9uZSBjYXNlIGZvciB0aHJlZSBwcmltZXMsIHByaW50IGFueSBjYXNlIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d