题目描述

小瓜特别喜欢一些奇特的数字。例如：给出一个整数 $x$ ，如果能够找到两个整数 $a,b$，满足 $x=a^2+b^2$，那么小瓜就认为这是一个奇特的数字。请你帮他去判断：$1 \sim n$ 中有多少奇特的数字。

输入格式

一个整数 $n$

输出格式

一个整数，表示奇特的数字的数量

样例

5

4

样例 $1$ 解释

在 $1 \sim 5$ 中，奇特的数字有 $1,2,4,5$ 四个数：

$1=0^2+1^2$

$2=1^2+1^2$

$4=0^2+2^2$

$5=1^2+2^2$

数据范围

对于 $30\%$ 的数据，$1≤n≤100$；

对于 $70\%$ 的数据，$1≤n≤10^3$；

对于 $100\%$ 的数据，$1≤n≤10^5$。