题目描述

数学老师给"勾股小队"出了一道题：

从 $1 \sim n$ 这 $n$ 个整数中挑出三个数 $a$、$b$、$c$（允许相同），要求满足 $a \le b \le c$ 且 $a^2 + b^2 = c^2$。

请你算出一共有多少种不同的挑法。

两种挑法不同，当且仅当它们的 $a$、$b$、$c$ 不完全相同。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示满足条件的挑法总数。

样例 #1

样例输入 #1

20

样例输出 #1

6

样例解释

这 $6$ 组分别是：$(3,4,5)$、$(6,8,10)$、$(5,12,13)$、$(9,12,15)$、$(8,15,17)$、$(12,16,20)$。

样例 #2

样例输入 #2

4

样例输出 #2

0

提示

数据范围

• 对于 $40\%$ 的数据：$n \le 50$；
• 对于 $100\%$ 的数据：$1 \le n \le 300$。

提示

• 只需要枚举 $a$ 和 $b$（两重循环），$c$ 可以直接由 $a^2 + b^2$ 开平方得到，不必再套第三重循环。
• sqrt 的返回值是 double（小数），带有微小的误差，不能直接拿来判断是否为整数。正确做法是先把它转成整数 $c$，再用乘法回验 $c \times c$ 是否真的等于 $a^2 + b^2$。