Unique right triangle

Time limit1sMemory limit256 MB

Summary

Count the perimeters up to N that form exactly one integer-sided right triangle.

Level: Medium7 of 10
Topics: Number theory, Array, Prefix sum
Solved: No attempts yet

Problem

12cm is the shortest length of string that can be bent into a right triangle whose three sides are all integers. Here are a few more such lengths.

12cm: (3, 4, 5)
24cm: (6, 8, 10)
30cm: (5, 12, 13)
36cm: (9, 12, 15)
40cm: (8, 15, 17)
48cm: (12, 16, 20)

A string of length 20cm cannot be bent into a right triangle with integer sides in any way.

Some lengths give several different right triangles. For example, 120cm gives three.

120cm: (30, 40, 50), (20, 48, 52), (24, 45, 51)

Let $L$ be the length of the string. Among the values $L \le N$ , how many give exactly one right triangle with integer sides? Triangles that differ only in the order of the sides count as the same triangle.

Input

The input holds several tests. Each line has one integer $N$ , and the tests continue to the end of the input. ( $1 \le N \le 20\,000\,000$ )

Output

For each test, print on its own line the number of values $L \le N$ that give exactly one right triangle with integer sides.

Examples2

Example 1
Input
```
12
30
```
Expected output
```
1
3
```
Example 2
Input
```
1
2
11
```
Expected output
```
0
0
0
```