小爱正在学习完全平方数的知识，他知道若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。

但好学的他发现有些完全平方数也能写成其他两个数字的乘积，例如：16=2 \times 8=4 \times 4,他把(2,8)这样乘积是完全平方数的数对，称为 完全平方数对，当然 (4,4) 本身也是完全平方数对。

现给定一个正整数 n，请你求出在数对中数字均不超过 n 的情况下，有多少对完全平方数对？

输入一个正整数，表示 $n$。

输出满足条件的数对个数。

对于30%的数据：1≤n≤50

对于60%的数据：1≤n≤10000

对于100%的数据：1≤n≤100000

样例解释

(1,1),(1,4),(2,2),(3,3),(4,1),(4,4),(5,5)共7对。