Problem Description

Everybody knows Goldbach Conjecture! Here is one edition of it:

1) Every odd integer greater than 17 can be written as three different odd primes’ sum;
2) Every even integer greater than 6 can be written as two different odd primes’ sum.

Loving the magical math conjecture very much, iSea try to have a closer look on it. Now he has a new definition: Goldbach Division. If we express an even integer as two different odd primes’ sum, or odd integer as three different odd primes’ sum, we call it a form of Goldbach Division of N, using a symbol G(N).

For example, if N = 18, there are two ways to divide N.
18 = 5 + 13 = 7 + 11
If N = 19, there is only one way to divide N.
19 = 3 + 5 + 11

Here comes your task, give a integer N, find |G(N)|, the number of different G(N).

Input

There are several test cases in the input.

Each test case includes one integer N (1 <= N <= 20000).

The input terminates by end of file marker.

Output

For each test case, output one integer, indicating |G(N)|.

18
19

2
1

Hint

There may be 2000 cases, be careful.

Author

iSea @ WHU