题目背景

PA 2025 R3C.

题目描述

一个底面尺寸为 $a\times b$，高为 $h$ 的长方体水箱的对角线长度为 $\sqrt{a^2+b^2+h^2}$。这里，$a,b,h$ 均为正整数。

求出有多少个本质不同的水箱满足以下条件：

• $\sqrt{a^2+b^2+h^2}\in \mathbb{Z}$；
• $\sqrt{a^2+b^2+h^2}\le n$。

定义两个水箱 $a_1,b_1,h_1$，$a_2,b_2,h_2$ 本质不同，当且仅当 $\{a_1,b_1\}\neq \{a_2,b_2\}$ 或者 $h_1\neq h_2$。

输入格式

一行一个正整数 $n$。

输出格式

一行一个非负整数，表示答案。

7

7

提示

样例解释

满足条件的水族箱如下：

• 底面形状 $1 \times 2$，高为 $2$，对角线长为 $3$。
• 底面形状 $2 \times 2$，高为 $1$，对角线长为 $3$。
• 底面形状 $2 \times 4$，高为 $4$，对角线长为 $6$。
• 底面形状 $4 \times 4$，高为 $2$，对角线长为 $6$。
• 底面形状 $2 \times 3$，高为 $6$，对角线长为 $7$。
• 底面形状 $2 \times 6$，高为 $3$，对角线长为 $7$。
• 底面形状 $3 \times 6$，高为 $2$，对角线长为 $7$。

数据范围

• $1 \leq n \leq 5000$。