P2563 [AHOI2001] Prime Sum Decomposition

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.

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

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

Translated by ChatGPT 5