#704. 小S的平方和

小S的平方和

题目描述

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

输入格式

给定一个正整数n。

输出格式

输出相应的答案。

样例 #1

样例输入 #1

10

样例输出 #1

7

提示

30%的数据保证,n100n\le100

70%的数据保证,n103n\le10^3

100%的数据保证,n105n\le10^5