题目描述

给定一个正整数 $N$。

请你计算满足以下条件的 $3$ 个正整数组 $(x, y, z)$ 的个数，并将结果对 $998244353$ 取模。

-任意两数之积都不超过 $N$。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入以以下格式从标准输入读入。

其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每个测试用例为一行，包含一个整数 $N$。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

输入输出样例 #1

输入 #1

4
1
2
5
998244353

输出 #1

1
4
17
727512986

说明/提示

限制

• $1 \leq T \leq 5000$
• $1 \leq N \leq 10^9$

样例解释 1

对于第 $1$ 个测试用例，$N=1$。满足条件的 $(x, y, z)$ 只有 $(1,1,1)$ 这 $1$ 个。

对于第 $2$ 个测试用例，$N=2$。满足条件的 $(x, y, z)$ 有 $(1,1,1)$、$(2,1,1)$、$(1,2,1)$、$(1,1,2)$ 共 $4$ 个。

由 ChatGPT 4.1 翻译