C. Prime
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Besides the delicacy that is freshmen blood drank during the Halloween night, Luna also enjoys prime numbers a lot... and the number 3... so she gives you a number $$$N$$$ and demands the number of different ways that the number $$$N$$$ can be written as a sum of 3 prime numbers.

Because you won't risk getting your blood drank by Luna, you decide to answer her demands.

Input

The only line of input contains one integer $$$N$$$ ($$$ 1 \leq N \leq 5\cdot 10^4$$$)

Output

Output a single integer - the number of ways to write $$$N$$$ as sum of 3 prime numbers.

Scoring
  • for 40 points it is guaranteed that $$$N \leq 100$$$
  • for another 30 points it is guaranteed that $$$N \leq 5000$$$
  • for the other 30 points, $$$N \leq 5\cdot 10^4$$$
Example
Input
7
Output
1
Note

The only correct way of expressing 7 as sum of 3 prime numbers is $$$7=2+2+3$$$. Permutations of the same prime numbers won't count (such as $$$2+3+2$$$)