Weaker Goldbach

In 1742 Christian Goldbach wrote to Leonhard Euler that, in his opinion, every integer $n > 5$ is a sum of three primes. (A prime is an integer $n > 1$ whose only positive divisors are $1$ and $n$.) Euler replied that this claim is equivalent to the statement that every even number $n \ge 4$ is a sum of two primes. Neither remark brought them closer to the underlying question: is it actually true? Today the statement has been verified for numbers up to $10^{11}$, and much more is known, yet the conjecture is still open.

We will not try to settle it. Instead we solve a more modest problem that relies on the following fact: every integer $n \ge 10$ can be written as a sum of distinct odd primes.

Given several integers, decompose each of them into a sum of distinct odd primes.

Because a number can usually be split in many ways, we ask for a single well-defined answer: use as few primes as possible, and if several decompositions attain that minimum, output the lexicographically smallest one (compare the two ascending lists element by element).

The first line contains one positive integer $n$ ($n \le 40$). Each of the next $n$ lines contains one integer $k$ from the interval $[10, 2{,}000{,}000{,}000]$.

For each integer $k$, print its decomposition on two lines. The first line contains one integer $m \ge 1$, the number of primes in the decomposition. The second line contains those $m$ distinct odd primes in ascending order, separated by single spaces; their sum equals $k$.

Among all decompositions of $k$ into distinct odd primes, output the one that uses the fewest primes; if several use that same minimum number, output the lexicographically smallest such list. Print the decompositions in the same order as the integers in the input.