EPIC1301 - Prime Summation

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

Added by:BYU Admin
Date:2013-03-20
Time limit:2s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.