You have decided to buy a new aquarium for your goldfish. In the aquarium shop, you have a very large selection: you can buy a rectangular cuboid aquarium with a base of $a \times b$ and height $h$ for any positive integer dimensions $a, b,$ and $h$.

Your fish likes to do morning exercises and, as a warm-up, swims back and forth along one of the diagonals of the aquarium. The length of the aquarium's diagonal is given by the formula $\sqrt{a^2 + b^2 + h^2}$.

To make it easier for the fish to calculate how far it has swum on a given day, you want the length of the diagonal to also be an integer. An aquarium that is too large is out of the question, so the length of its diagonal must be at most $n$.

How many different aquariums meet all the requirements? Two aquariums are considered different if they have a different height or a different unordered pair $\{a, b\}$ (an aquarium with base $a \times b$ and height $h$ is the same as an aquarium with base $b \times a$ and height $h$).

Due to the nature of this problem, sharing tests for this task on the forum is prohibited!

Input

The only line contains a single integer $n$ ($1 \le n \le 5000$), representing the limit on the aquarium's diagonal.

Output

Output a single integer — the number of different aquariums that satisfy the problem conditions.

Examples

Input 1

7

Output 1

7

Note

The possible aquariums are: Base $1 \times 2$, height $2$, diagonal $3$. Base $2 \times 2$, height $1$, diagonal $3$. Base $2 \times 4$, height $4$, diagonal $6$. Base $4 \times 4$, height $2$, diagonal $6$. Base $2 \times 3$, height $6$, diagonal $7$. Base $2 \times 6$, height $3$, diagonal $7$. * Base $3 \times 6$, height $2$, diagonal $7$.