Problem Description

The conclusion of Hilbert's tenth problem shows that it's impossible to design an algorithm to calculate the integral solutions of an arbitrary equation. But for some simple equation, we can easily check it.

For example, to check if there exist two integers $x,y$ which satisfy $x^2 + y^2 = a$ and $xy =b$: We can calculate $x+y = \pm \sqrt{a+2b},x-y=\pm\sqrt{a-2b}$ and then check if both $x$ and $y$ could be integers.

Rikka thinks this task is too simple and she wants to make it look harder. Rikka knows, sometimes if you consider the equality after modulo $m$, the task will be different. So, she wants to do the same thing to this problem.

She call a tuple $(a,b,m)(0 \leq a,b < m)$ valid if and only if there exist two integers $x$ and $y$ which satisfy $x^2+y^2\equiv a \mod m, xy\equiv b \mod m$. After showing you a positive integer $n$, she wants you to calculate the number of valid tuples $(a,b,m)$ with $m \leq n$.

Input

The first line contains a single integer $t(1 \leq t \leq 10^5)$, the numebr of the testcases.

For each testcase, the first line contains a single number $n(1 \leq n \leq 10^7)$.

Output

For each testcase, output a single line with a single integer, the answer modulo $998244353$.

5
3
5
10
100
1000

8
22
104
45933
32791150