Description

有 $T$ 次询问。每次给定 $n$，求合法集合的个数。

定义一个集合 $S$ 合法，当且仅当：

• $S\subseteq \{x:x\mid n\},S\ne \varnothing,\min(S)\ge 2$.

• $\forall x,y \in S(x \neq y),\gcd(x,y)=1$.

请输出答案对 $998244353$ 取模后的结果。

Format

Input

第一行，一个正整数 $T$，表示询问次数。

接下来 $T$ 行，每行一个正整数 $n$。

Output

共 $T$ 行，第 $k$ 行表示第 $k$ 次询问的答案。

Samples

3
2
4
6

1
2
4

在第一组数据中，$n=2$，只有集合 $\{2\}$ 满足条件。

在第二组数据中，$n=4$，只有集合 $\{2\}$ 与 $\{4\}$ 满足条件。但是集合 $\{2,4\}$ 不满足条件，因为 $\gcd(2,4) \neq 1$；集合 $\{3\}$ 也不满足条件，因为 $3 \nmid n$。

在第三组数据中，$n=6$，只有集合 $\{2\},\{3\},\{6\},\{2,3\}$ 满足条件。

6
97
94
98
997
973
969

1
4
7
1
4
14

5
12345
123456
10000
100000
1000000

14
64
40
60
84

其余样例见下发文件。

Limitation

对于 $100\%$ 的数据，保证 $1\le T\le 10^6,1 \le n \le 10^8$。

可能需要更快的输入输出方式。

下表中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数。

附加文件set.zip