#PYTRIP3. Counting Pythagorean Triples

Counting Pythagorean Triples

We define a Pythagorean triple as a set of three positive integers $a$, $b$ and $c$ which satisfy $a^2 + b^2 = c^2$.

Let $P(N)$ denote the number of Pythagorean triples whose hypotenuses ($= c$) are less than or equal to $N$ (i.e. $c \le N$).

Given $N$, find $P(N)$.

Input

The first line of input contains a positive integer $N$.

Output

Print on a single line the value of $P(N)$.

Constraints

$1 \le N \le 1234567891011$

Example

Input1:
5

Output1: 1

Input2: 15

Output2: 4

Input3: 10000

Output3: 12471

Input4: 1000000000000

Output4: 4179478903392

</p>

Explanation for Input2

There are four Pythagorean triples: $\{3, 4, 5\}$, $\{5, 12, 13\}$, $\{6, 8, 10\}$, $\{9, 12, 15\}$

Information

There are 15 test cases.

The sum of the time limits is 93 sec. (My solution runs in 5.4 sec.)

Source Limit is 5 KB.