P1951 [Aboi 2077] SL2(Z/NZ)


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)] $$

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.

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

| Subtask ID | $N$ | Score | | :-----------: | :-----------: | :-----------: | | 1 | $\le 50$ | 10 | | 2 | $\le 200$ | 10 | | 3 | $\le 10^3$ | 20 | | 4 | $\le 10^6$ | 20 | | 5 | $\le 10^9$ | 20 | | 6 | $\le 10^{18}$ | 20 | For all testdata, $1 \le T \le 10$, $1 \le N \le 10^{18}$. Translated by ChatGPT 5