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 data

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

Output data

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

Constraints and clarifications

• For $40$ points it is guaranteed that $N \leq 100$;
• For another $30$ points it is guaranteed that $N \leq 5 \ 000$;
• For the other $30$ points, $N \leq 5\cdot 10^4$.

Example

stdin

7

stdout

3

Explanation

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$)