K. Equal Difference Prime
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Hile likes prime numbers very much.

Now he wants you to count how many quadruples $$$a, b, c, d$$$ $$$(1 \le a \lt b \lt c \lt d \le n)$$$ satisfy $$$b-a=c-b=d-c$$$ and $$$a, b, c, d$$$ are all prime numbers.

Input

The input contains only one integer $$$n$$$ $$$(1 \le n \le 10^6)$$$.

Output

Print one integer — the number satisfying the conditions above.

Example
Input
23
Output
1
Note

The only quadruples for the test case are $$$(5, 11, 17, 23)$$$.