PYTRIP3 - Counting Pythagorean Triples

We define a Pythagorean triple as a set of three positive integers aa, bb and cc which satisfy a2+b2=c2a^2 + b^2 = c^2.

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

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

Input

The first line of input contains a positive integer NN.

Output

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

Constraints

1N12345678910111 \le N \le 1234567891011

Example

Input 1:
5

Output 1:
1
Input 2:
15

Output 2:
4
Input 3:
10000

Output 3:
12471
Input 4:
1000000000000

Output 4:
4179478903392

Explanation for Input 2

There are four Pythagorean triples: {3,4,5}\{3, 4, 5\}, {5,12,13}\{5, 12, 13\}, {6,8,10}\{6, 8, 10\}, {9,12,15}\{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.


Added by:Min_25
Date:2014-05-26
Time limit:1s-15s
Source limit:5120B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2022-08-07 14:59:26
I wanted to solve this problem one year ago,now I finally solve it.
Amazing Problem!
2016-01-12 03:19:44 nguyễn vãn lâm
@francky sorry. i was wrong, the problem limited n = 10^4, and i solved it. but my solution cannot apply for above problem
2016-01-08 08:57:18 nguyễn vãn lâm
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
2014-10-19 11:06:29 Szegedi Gábor
What faster way there is to generate all primitive triplets than using the Tree of primitive Pythagorean triples?
2014-10-19 11:06:29 wisfaq
Nice problem!

[Re: Thank you !]

Last edit: 2014-05-30 19:48:16
2014-10-19 11:06:29 Min_25
@Francky
Thank you. This task is not easy, but the intended solution is relatively simple.

Last edit: 2014-05-26 17:43:26
2014-10-19 11:06:29 Francky
My "brute force" program took 2h to check sample #4. I need a better approach ; I'll find it ! Thanks for that task.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.