You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定 $N$，求有多少个不同的三元组 $(x, y, z)$ 满足：

• $1 \le x \le y \le z \le N$；
• $x \mid y$；
• $y \mid z$；

其中 $a \mid b$ 表示 $b \equiv 0\pmod a$。

输入

本题共有 $T$ 组测试数据，共输入 $T + 1$ 行。

• 第 $1$ 行：$1$ 个整数 $T$，表示测试数据数量。
• 第 $2 \sim T + 1$ 行，第 $q + 1$ 行表示第 $q$ 组测试数据。

对于每组测试数据：

• 输入 $1$ 个整数 $N$。

输出

共输出 $T$ 行：

• 第 $q$ 行：$1$ 个整数表示测试数据 $q$ 的答案。

样例

2
3
314159

7
28227166

若 $n = 3$，则满足条件的三元组如下：

• $(1, 1, 1)$，$(1, 1, 2)$，$(1, 1, 3)$，$(1, 2, 2)$，$(1, 3, 3)$，$(2, 2, 2)$，$(3, 3, 3)$

数据范围

• 对于 $100\%$ 的数据，$11 \le T \le 54$，$1 \le N \le 1000$。
• 提示：你可以通过 $T$ 的个位数判断此测试点属于哪个 $\text{Subtask}$。