약한 골드바흐

1742년 크리스티안 골드바흐는 레온하르트 오일러에게 보낸 편지에서, $5$보다 큰 모든 정수 $n$은 세 소수의 합이라고 주장했습니다. (소수란 양의 약수가 $1$과 자기 자신뿐인, $1$보다 큰 정수입니다.) 오일러는 이 주장이 “$4$ 이상의 모든 짝수 $n$은 두 소수의 합”이라는 명제와 동치라고 답했습니다. 그러나 두 사람 모두 근본적인 질문, 즉 이것이 정말 참인지에는 다가가지 못했습니다. 오늘날 이 명제는 $10^{11}$까지의 수에 대해 성립함이 확인되었고 그 밖에도 많은 것이 알려져 있지만, 이 추측은 여전히 미해결로 남아 있습니다.

우리는 이 추측을 증명하려는 것이 아니라, 다음 사실을 이용해 조금 더 쉬운 문제를 풉니다. $10$ 이상의 모든 정수 $n$은 서로 다른 홀수 소수들의 합으로 나타낼 수 있습니다.

여러 개의 정수가 주어질 때, 각 정수를 서로 다른 홀수 소수들의 합으로 분해하세요.

한 수를 분해하는 방법은 보통 여러 가지이므로, 답이 하나로 정해지도록 다음 규칙을 따릅니다. 사용하는 소수의 개수가 가장 적은 분해를 고르고, 그런 분해가 여러 개라면 오름차순으로 나열한 두 목록을 원소별로 비교했을 때 사전순으로 가장 앞서는 것을 출력합니다.

첫째 줄에 양의 정수 $n$ ($n \le 40$)이 주어집니다. 이어지는 $n$개의 줄에는 각각 구간 $[10, 2{,}000{,}000{,}000]$에 속하는 정수 $k$가 하나씩 주어집니다.

각 정수 $k$에 대해 분해 결과를 두 줄에 출력합니다. 첫째 줄에는 분해에 사용된 소수의 개수 $m \ge 1$을 출력합니다. 둘째 줄에는 서로 다른 홀수 소수 $m$개를 오름차순으로, 공백 하나로 구분하여 출력합니다. 이들의 합은 $k$와 같아야 합니다.

$k$를 서로 다른 홀수 소수들의 합으로 분해하는 모든 방법 중에서 사용하는 소수의 개수가 가장 적은 것을 출력하고, 그런 분해가 여러 개라면 사전순으로 가장 앞서는 목록을 출력합니다. 분해 결과는 입력에 주어진 정수와 같은 순서로 출력합니다.