Jimp Numbers

Time limit2sMemory limit512 MB

Summary

Count the jimp numbers k up to n, where exactly one arithmetic triple (a, b, c) satisfies a^2 + b^2 + k = c^2.

Level: Hard8 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

A positive integer $k$ is called a jimp number if there is exactly one triple of positive integers $(a, b, c)$ such that $a$ , $b$ , and $c$ are consecutive terms of an arithmetic progression, in that order, and $a^2 + b^2 + k = c^2$ .

Count the jimp numbers that are not greater than the given number $n$ .

Input

The only line contains a single integer $n$ ( $1 \le n \le 10^{11}$ ).

Output

Print a single integer: the number of jimp numbers not greater than $n$ .

Examples2

Example 1
Input
```
5
```
Expected output
```
2
```
Example 2
Input
```
100
```
Expected output
```
25
```