P1951 [Aboi 2077] SL2(Z/NZ)
题目背景
题目描述
求模 $N$ 意义下行列式为 $1$ 的 $2\times2$ 矩阵数量。
即：
$$
\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)]
$$
输入格式
多组数据，第一行一个正整数 $T$ 表示数据组数。
之后 $T$ 行，每行一个正整数 $N$，表示该组数据的模数。
输出格式
对于每组数据，输出答案模 $998244353$ 的值。
说明/提示
| 子任务编号 | $N$ | 分值 |
| :-----------: | :-----------: | :-----------: |
| $1$ | $\le50$ | $10$ |
| $2$ | $\le200$ | $10$ |
| $3$ | $\le10^3$ | $20$ |
| $4$ | $\le10^6$ | $20$ |
| $5$ | $\le10^9$ | $20$ |
| $6$ | $\le10^{18}$ | $20$ |
对于所有数据，$1\le T\le10$，$1\le N\le10^{18}$。