Description

Any natural number $n$ greater than $1$ can be written as a sum of primes each greater than or equal to $2$ and less than or equal to $n$ (including the case where the sum consists of only one number), and there may be more than one such prime-sum form. For example, the prime-sum expressions of $9$ have four essentially different forms:

$9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7$。

Two expressions are considered essentially the same if one can be obtained from the other by permuting the addends.

Write a program to compute how many essentially different prime-sum expressions a natural number $n$ can have.

Input Format

Each line of the file contains a natural number $n$ ($2 \leq n \leq 200$).

Output Format

For each natural number $n$, output the number of essentially different prime-sum expressions.

2
200

1
9845164

Hint

Translated by ChatGPT 5