짐프 수

시간 제한2초메모리 제한512 MB

요약

등차수열을 이루는 연속한 세 항 a, b, c가 a^2 + b^2 + k = c^2을 만족하는 경우가 정확히 하나인 양의 정수 k의 개수를 n 이하에서 구합니다.

문제

양의 정수 $k$ 에 대해, $a$ , $b$ , $c$ 가 이 순서대로 등차수열의 연속한 항이고 $a^2 + b^2 + k = c^2$ 를 만족하는 양의 정수 세쌍 $(a, b, c)$ 가 정확히 하나만 있으면 $k$ 를 짐프 수라고 한다.

주어진 정수 $n$ 이하인 짐프 수의 개수를 구하라.

첫째 줄에 정수 $n$ 이 주어진다 ( $1 \le n \le 10^{11}$ ).

$n$ 이하인 짐프 수의 개수를 한 개의 정수로 출력한다.