该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小S特别喜欢一些奇特的数字，例如10，因为10可以表示成$1^2 + 3^2$ 。一个数字如果能表示成两个平方数之和，那么小S就认为这是一个奇特的数字，但是奇特的数字的拆分很难去实现，那么小S拜托你帮助他去判断$1到n$中有多少奇特的数字，特别的是0也是平方数，平方数是指整数的平方。

输入格式

给定一个正整数n。

输出格式

输出相应的答案。

样例 #1

样例输入 #1

10

样例输出 #1

7

提示

30%的数据保证，$n\le100$

70%的数据保证，$n\le10^3$

100%的数据保证，$n\le10^5$