Rikka with Equation

The conclusion of Hilbert's tenth problem shows that no algorithm can find all integer solutions of an arbitrary system of equations. However, some simple equations are still easily solvable.

For example, how do we check whether there exist two integers $x$ and $y$ that satisfy $x^2 + y^2 = a$ and $xy = b$? We can compute $x + y = \pm \sqrt{a + 2b}$ and $x - y = \pm \sqrt{a - 2b}$, and then check whether both $x$ and $y$ can be integers.

Rikka thinks this task is too simple, so she wants to make it look harder. Rikka knows that sometimes considering an equation modulo $m$ makes the problem different. So she wants to do the same with this problem.

A tuple $(a, b, m)$ with $0 \leq a, b < m$ is valid if and only if there exist two integers $x$ and $y$ that satisfy $x^2 + y^2 \equiv a \pmod{m}$ and $xy \equiv b \pmod{m}$. Given a positive integer $n$, count the number of valid tuples $(a, b, m)$ with $m \leq n$. Since this number may be large, output it modulo $998\,244\,353$.

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. Each test case is given on a separate line containing a single integer $n$ ($1 \leq n \leq 10^7$).

For each test case, output a single line containing the number of valid tuples modulo $998\,244\,353$.