## PYTRIP3 - 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

### 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. nguyễn vãn lâm: 2016-01-12 03:19:44 @francky sorry. i was wrong, the problem limited n = 10^4, and i solved it. but my solution cannot apply for above problem nguyễn vãn lâm: 2016-01-08 08:57:18 oh. unbelievable, spoj world has only 2 people solve this problem. in vietnam, there are 45 people solved successfully. but i'm not in there! =(Francky)=> Check again constraints !!! And give a try at PYTRIP2 too. Last edit: 2016-01-13 03:57:07 Szegedi Gábor: 2014-10-19 11:06:29 What faster way there is to generate all primitive triplets than using the Tree of primitive Pythagorean triples? wisfaq: 2014-10-19 11:06:29 Nice problem! [Re: Thank you !] Last edit: 2014-05-30 19:48:16 Min_25: 2014-10-19 11:06:29 @Francky Thank you. This task is not easy, but the intended solution is relatively simple. Last edit: 2014-05-26 17:43:26 Francky: 2014-10-19 11:06:29 My "brute force" program took 2h to check sample #4. I need a better approach ; I'll find it ! Thanks for that task.