在银河中孤独摇摆

时间限制：1000ms $\enspace$ 空间限制：512MB

题目背景

知更鸟小姐是闻名银河的歌者。

在一次外出演出的途中，知更鸟小姐乘坐的飞船遇到了一条小行星带，里面有数不胜数的小行星，为了继续前行，飞船必须使用激光武器消除掉一些小行星。然而，飞船的武器能源储备十分有限，知更鸟小姐的时间也非常紧张，根本无法消除所有小行星。

万幸，船长发现只需要消灭一部分小行星就可以让飞船继续前行，于是他联系到了你，希望你帮助他统计一下总共有多少必须消灭的小行星。

题目描述

小行星带共有 $n$ 个小行星，每个小行星有一个编号，从 $1$ 到 $n$。当且仅当一个小行星的编号可以被表示为某两个正整数平方的和时，它是必须被消除的。

例如：

• $2=1^2+1^2$，故 $2$ 号小行星是必须被消除的。
• $3$ 无法被表示为两正整数的平方和，故 $3$ 号小行星不是必须被消除的，
• $5=2^2+1^2$，故 $5$ 号小行星是必须被消除的。

现在，请你统计出这 $n$ 个小行星中有多少是必须被消除的。

输入格式

一行一个正整数 $n$。

输出格式

一行一个非负整数，代表这 $n$ 个小行星中必须被消除的小行星个数。

输入输出样例

见下发文件（点击下载）。

数据范围及约定

对于 $40\%$ 的数据，满足 $1\le n\le 100$。

对于 $60\%$ 的数据，满足 $1\le n\le 10^3$。

对于另外 $10\%$ 数据，满足 $n=114514$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^7$。

后记

Rise ~ Up into my world .