Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2414
Index of Prime

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Let P1, P2, P3....be a sequence of prime numbers. Index of prime for number is 0 iff it is impossible to present it as a sum of few (maybe one) prime numbers, and if such presentation exists, index is equal to minimal number of items in such presentation. Your task is to find index of prime for given numbers and find optimal presentation as a sum of primes.

Input

There are several test cases. Each test case contains a number which is not more than 10000 in a line.

Output

For each test case, first output the index I for the corresponding given number in a line and then write I prime numbers that are items in optimal presentation for the given number. Write these I numbers in order of non-increasing. If there is a tie, output the one in order of smallest dictionary order.

Sample Input

6

Sample Output

2
3 3

Author: HUANG, Ninghai
Source: Zhejiang University Local Contest 2005
Submit    Status