**5 人解决**，17 人已尝试。

**6 份提交通过**，共有 83 份提交。

**8.6** EMB 奖励。

**单点时限: **0.5 sec

**内存限制: **256 MB

*In the beginning, there were no primes, or numbers. And God said, “let there be numbers,” and there were numbers. God thought that it might be a beautiful thing to have some of these numbers added up, and he called some of the sums “primes”.*

Some scholars argued that there should be no more than $8$ numbers God first created, as the largest prime written in these ancient books was $233$. But others found this not convincing, as it was debatable whether $233$ was a prime.

If the legend somehow confuses you, here is a more formal version:

Find out the smallest positive integer $k$ such that there is a set (non-repeated) of positive integers $X$ where $|X|=k$, and any prime number in ${1,2,\ldots,n}$ can be expressed as the sum of a subset of $X$.

The input only consists of one line $n$ ($1 \le n \le 233$).

Output the smallest $k$ in the first line.

Then output $k$ positive integers separated with space, denoting $X$. You can output the set in any order you want. The numbers should be distinct. You should not output any number larger than $10^9$. (it doesn’t make sense anyway.)

Input

2

Output

1 2

Input

5

Output

2 2 3

Input

10

Output

3 2 1 4

Explanation of example 3: primes no larger than $10$ are $2, 3, 5, 7$. $2=2$, $3=1+2$, $5=1+4$, $7=1+2+4$.

**Hint: The time limit is deliberately set to be very tight.**

**5 人解决**，17 人已尝试。

**6 份提交通过**，共有 83 份提交。

**8.6** EMB 奖励。

题目标签