Welcome to ZOJ
Select Problem
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.


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


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


Sample Output

3 3

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