Migrated from Lutece 1391 LRZ and Ellipses

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Recently, the beauty of the mathematics fetched LRZ completely. Today, LRZ construct an ellipse $E_0$ with function $x^2+4y^2=4a^2$. Now she find that she can rotate this ellipse by $t$ ($t\in (0, 90)$)degrees counterclockwise around the original point $O(0,0)$ to get a new ellipse $E_1$.

You can understand this action as the following picture:

LRZ define $c$ as the length of the segment of $OC$ and $b$ as the length of the segment of $OB$

$C$ is the point of the intersection of $E_0$ and $E_1$ in the first quadrant.

$B$ is the point of the intersection of $E_0$ and $E_1$ in the second quadrant.

For an integer $a$, if LRZ can find an angle $t\in (0,90)$, so that $b$ and $c$ are also integers, she will call the triple $(a,b,c)$ a lucky triple.

Now LRZ is wondering, how many distinct lucky triples are there for $a$ from 1 to $N$(inclusive).

For some stupid reasons we can regard triple $(a,b,c)$ and triple $(a,c,b)$ as the same triple.

$1\le N\le 1000000000$

Input

An integer $N$

Output

You should output the number of lucky triples.

Samples

1000

7

Resources

IEEEXTREME Programming Competition