题目描述

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

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

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

输入格式

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

输出格式

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

5

7

样例解释 1

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

数据范围

• 对于$30\%$的数据：$1 \leq n \leq 50$
• 对于$60\%$的数据：$1 \leq n \leq 10^4$
• 对于$100\%$的数据：$1 \leq n \leq 10^5$