问题陈述

给定一个正整数 $N$。找到满足以下条件的正整数三元组 $(x,y,z)$ 的数量（对 $998244353$ 取模）。

• $xy$、$yz$ 和 $zx$ 都小于或等于 $N$。

你需要解决 $T$ 个测试用例。

约束条件

• $1 \le T \le 100$
• $1 \le N \le 10^9$

输入

输入以以下格式从标准输入给出，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

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

每个测试用例的格式如下：

$N$

输出

打印 $T$ 行。第 $i$ 行（$1 \le i \le T$）应该包含第 $i$ 个测试用例的答案。

示例输入 1

4
1
2
5
998244353

示例输出 1

1
4
17
727512986

在第一个测试用例中，$N=1$。满足条件的三元组 $(x,y,z)$ 是 $(1,1,1)$，数量为 $1$。

在第二个测试用例中，$N=2$。满足条件的三元组 $(x,y,z)$ 是 $(1,1,1),(2,1,1),(1,2,1),(1,1,2)$，数量为 $4$。