问题描述

设一个数的质因子分解为 $$ n=\prod_{i=1}^wp_i^{q_i} $$ 定义函数 $$ F(n)=\prod_{i=1}^wp_i^{k_i} $$ 其中 $$ k_i=\frac{q_i}{\gcd(q)} $$ 求 $$ \sum_{i=2}^nF(i) $$ 输出答案对998244353取模的结果。

输入格式

多组数据，第一行一个数$T$表示数据组数。 后面$T$行，每行一个数$n$。

输出格式

$T$行，每行一个数，表示答案。

样例一

input

6
120
121
124
125
44761
31415926535897932384626433832795

output

6855
6866
7235
7240
2741
382417086

数据规模

subtask1(8')：$T=1000,n \leq 10^7$。

subtask2(32')：$T = 600,n \leq 10^9$。

subtask3(14')：$T=1000,n \leq 10^{18}$。

subtask4(20')：$T=1,n \leq 10^{500}$。

subtask5(26')：$T=1,n \leq 10^{1200}$。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$