Problem Description

有一个$ n-1 $个点的无向图， 每个点的编号为$ 2..n $

两个点$ u, v $ 之间存在一条边当且仅当 $ u $ 是 $ v $ 的倍数或者 $ v $ 是 $ u $ 的倍数

我们用$ c(u, v) $ 来描述两个点之间的联通状态, 用$\phi(x)$表示欧拉函数， 即$ 1..x-1 $中有多少个数与他互质

求 $$ \sum_{u = 2} ^ {n - 1} \sum_{v = u + 1} ^ {n} c(u, v) \phi(u) \phi(v) $$

Input

第一行一个$ T $ 描述数据组数 $ 1 \leq T \leq 10^6 $

接下来$ T $行， 每行一个整数 $ n (1 \leq n \leq 10^7) $， 用来描述一组数据， 具体含义如上

Output

$ T $ 行， 每行一个数用来描述上述式子对 $998244353$ 取模的结果

10
1
2
3
4
5
6
7
8
9
10

0
0
0
2
2
18
18
46
112
264

Hint

对于n = 5， 那么只有$2, 4$联通， 所以答案是2