A prime summation of X is defined as a summation of a series of prime numbers that total X.  For example, 10 = 2+2+2+2+2.  Additionally, 10 = 5+3+2.  It turns out that there are five unique ways to write a prime summation of 10.

Given a number X, return the total number of unique prime summations for X.  Both X and the answer can be stored as an unsigned 32-bit integer.

Input

A single number, small enough to be stored as an unsigned 32-bit integer.

Output

The number of unique prime summations for the input.

Example

Input:
10

Output:
5