题目描述

波特发明了一种筛法——波特筛！

可惜的是，由于时间过于久远，波特已经忘记了如何实现这种筛法。不过，它还记得波特筛能够解决的问题。

设正整数 $n$ 的标准质因数分解为

其中 $p_i$ 两两不同且均为质数，$\alpha_i$ 为正整数。定义数论函数

特别地，空乘积为 $1$，因此 $f(1)=1$。

现在给定若干个 $n$，对于每次询问，你需要计算

输入格式

第一行包含一个整数 $T$，表示询问组数。

接下来 $T$ 行，每行包含一个整数 $n$，表示一次询问。

输出格式

输出共 $T$ 行。

对于每次询问，输出一行一个整数，表示

对 $998244353$ 取模后的结果。

样例

5
1
10
1000
1000000
10000000000

1
89
91403
555853215
441242777

数据范围

• 对于 $20\%$ 的数据，$n\le 10^5$；
• 对于 $40\%$ 的数据，$n\le 10^7$；
• 对于 $70\%$ 的数据，$T\le 5$，$n\le 10^9$；
• 对于全部数据，$1\le T\le 10$，$1\le n\le 10^{10}$。