Goldbach Division#1285

Goldbach Division

1 second
64 megabytes
Easy

Everyone knows the Goldbach Conjecture! Here is one version:

1) Any odd integer greater than can be written as the sum of three different odd primes. 2) Any even integer greater than can be written as the sum of two different odd primes.

Inspired by this famous mathematical problem, someone decided to study the Goldbach Conjecture in more detail and introduced a new term: Goldbach Division. If a number is even, we express it as the sum of two different odd primes; if it is odd, as the sum of three different odd primes. Such a way of expressing a given is called a Goldbach Division and is denoted as .

For example, if N = 18, there are two ways to express as required:

18 = 5 + 13 = 7 + 11

If N = 19, there is only one way to express as required:

19 = 3 + 5 + 11

Your task: given , find , that is, the number of different Goldbach Divisions for .

Input

The input contains several test cases.

Each test case is a single integer (1 \leq N \leq 20000), given on a separate line.

The input ends at end of file.

Output

For each test case, print on a separate line.

Examples

Example 1

Loading
Loading