[AdditionalFile4870.zip](file://AdditionalFile4870.zip?type=additional_file)

#4870. 「PA 2025」Akwarium

标签: 传统 | 时间限制: 10000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2025 Runda 3 Akwarium

你决定为心爱的金鱼买一个新鱼缸。在水族店里，选项多得让人眼花缭乱：你可以挑一个底面为 $a \times b$、高为 $h$ 的长方体鱼缸，$a$、$b$ 和 $h$ 都是任意正整数。

你的金鱼喜欢早上做运动，热身时会沿着鱼缸的一条对角线来回游。对角线的长度可以用公式 $\sqrt{a^{2}+b^{2}+h^{2}}$ 计算。为了让金鱼轻松算出每天游了多远，你希望对角线长度是个整数。但鱼缸也不能太大，对角线长度必须不超过 $n$。

请你算算，有多少种不同的鱼缸能满足这些要求？如果两个鱼缸的高度不同，或底面的无序对 $\{a, b\}$ 不同，则视为不同（底面为 $a \times b$、高为 $h$ 的鱼缸，与底面为 $b \times a$、高为 $h$ 的鱼缸算作同一个）。

输入格式

输入只有一行，包含一个整数 $n$ $(1 \leq n \leq 5000)$，表示鱼缸对角线的最大限制。

输出格式

输出一个整数，表示满足条件的不重复鱼缸数量。

样例

输入

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$。