题目背景

题目描述

求模 $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$ 的值。

10
2
5
11
23
101
64
128
114514
1919810
1145141919810

6
120
1320
12144
1030200
196608
1572864
173069674
546691096
761755430

提示

子任务编号	$N$	分值
$1$	$\le50$	$10$
$2$	$\le200$
$3$	$\le10^3$	$20$
$4$	$\le10^6$
$5$	$\le10^9$
$6$	$\le10^{18}$

对于所有数据，$1\le T\le10$，$1\le N\le10^{18}$。