Background

Special for beginners, ^_^

2024.6YACS(丙组) T3完全平方数对

Description

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

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

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

Format

Input

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

Output

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

Limitation

对于 $30\%$ 的数据, 满足 $1\leq n\leq300$ 。

对于 $60\%$ 的数据, 满足 $1\leq n\leq7\times10^{4}$ 。

对于 $100\%$ 的数据, 满足 $1\leq n\leq10^8$ 。

Samples

5

7

说明:

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