Tetrahedron

Problem Description

Generate three integers $a$, $b$, and $c$ in $[1,n]$ with equal probability independently, and use them as the three right-angle side length of a right-angled tetrahedron. Find the expectation of the reciprocal square of the distance from the right-angle apex to the slope (Euclidean distance). For each test case, output a line containing the answer mod $998244353$.

Input

In the first line, you should read an integer $T$ denoting the number of test cases. In every test case, the only line will include an integer $n$. It is guaranteed that $T$ is no larger than $2 \times 10^6$ and $n$ is no larger than $6 \times 10^6$.

Output

For each test case, output the only line containing just one integer denoting the answer mod $998244353$.

Sample Input

3
1
2
3

Sample Output

3
124780546
194103070

Source

2020 Multi-University Training Contest 5