希尔伯特第十问题的结论表明，设计一种算法来寻找任意方程组的所有整数解是不可能的。但对于一些简单的方程，这仍然是可行的。

例如，我们如何检查是否存在两个整数 $x$ 和 $y$ 满足 $x^2 + y^2 = a$ 且 $xy = b$？我们可以计算 $x + y = \pm \sqrt{a + 2b}$ 和 $x - y = \pm \sqrt{a - 2b}$，然后检查 $x$ 和 $y$ 是否均为整数。

Rikka 认为这个任务太简单了，她想让它看起来更难一些。Rikka 知道，有时如果你考虑模 $m$ 下的等式，问题就会变得不同。因此，她想对这个问题做同样的处理。

我们称一个元组 $(a, b, m)$ ($0 \le a, b < m$) 是合法的，当且仅当存在两个整数 $x$ 和 $y$ 满足 $x^2 + y^2 \equiv a \pmod m$ 且 $xy \equiv b \pmod m$。在给定一个正整数 $n$ 后，Rikka 希望你计算满足 $m \le n$ 的合法元组 $(a, b, m)$ 的数量。由于这个数字可能非常大，请将其对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。 每个测试用例占一行，包含一个整数 $n$ ($1 \le n \le 10^7$)。

输出格式

对于每个测试用例，输出一行，包含一个整数：合法元组的数量对 $998\,244\,353$ 取模的结果。

样例

输入 1

5
3
5
10
100
1000

输出 1

8
22
104
45933
32791150