Description

Count the number of $2 \times 2$ matrices with determinant equal to $1$ modulo $N$.

That is:

$$\sum_{a=0}^{N-1}\sum_{b=0}^{N-1}\sum_{c=0}^{N-1}\sum_{d=0}^{N-1}[ad-bc\equiv1\ (\bmod\ N)]$$

Input Format

Multiple test cases. The first line contains a positive integer $T$ indicating the number of test cases.

Then $T$ lines follow, each containing a positive integer $N$, the modulus for that test.

Output Format

For each test case, output the answer modulo $998244353$.

10
2
5
11
23
101
64
128
114514
1919810
1145141919810

6
120
1320
12144
1030200
196608
1572864
173069674
546691096
761755430

Hint

Subtask ID	$N$	Score
1	$\le 50$	10
2	$\le 200$
3	$\le 10^3$	20
4	$\le 10^6$
5	$\le 10^9$
6	$\le 10^{18}$

For all testdata, $1 \le T \le 10$, $1 \le N \le 10^{18}$.

Translated by ChatGPT 5