Sum of Three Primes

Interview

Time limit1sMemory limit256 MB

Summary

Read each odd K between 7 and 999 and print the lexicographically smallest triple of primes summing to K, or 0.

Level: Easy3 of 10
Topics: Number theory, Brute force
Solved: No attempts yet

Problem

In number theory, the 3-primes problem is the following conjecture.

"Every odd number greater than 5 can be written as a sum of three primes. The same prime may be added more than once."

For example, $7 = 2 + 2 + 3$ , $11 = 2 + 2 + 7$ , and $25 = 3 + 3 + 19$ .

Read an odd number $K$ greater than 5 and write $K$ as a sum of three primes.

Several triples can work, so the output is fixed to one of them. Sort each triple in ascending order as $(a, b, c)$ and choose the lexicographically smallest one: the smallest $a$ , and among those the smallest $b$ .

Input

The first line contains the number of test cases $T$ .

Each of the next $T$ lines contains one integer $K$ . $K$ is odd and $7 \le K < 1000$ .

Output

Print one line for each test case.

If $K$ can be written as a sum of three primes, print the lexicographically smallest triple in ascending order, separated by single spaces. Otherwise print 0.

Examples3

Example 1
Input
```
3
7
11
25
```
Expected output
```
2 2 3
2 2 7
3 3 19
```
Example 2
Input
```
1
7
```
Expected output
```
2 2 3
```
Example 3
Input
```
1
999
```
Expected output
```
3 5 991
```