拆分

题目描述

给定一个整数 $n$,求将 $n$ 分解为互不相同的不小于 $2$ 的数的乘积的方案数。答案模 $998244353$。

输入输出格式

输入格式


第一行一个整数 $T$,表示数据组数。 接下来 $T$ 行,每行一个整数 $n$,意义如描述所述。

输出格式


一共 $T$ 行,每行一个整数,表示答案。

输入输出样例

输入样例 #1

1
688

输出样例 #1

6

说明

样例中,因为 $688 = 2 \times 4 \times 86= 2 \times 8 \times 43= 2 \times 344= 4 \times 172= 8 \times 86= 16 \times 43$ 所以答案为 $6$ 对于 $10\%$ 的数据,保证 $n$ 为质数 对于 $20\%$ 的数据,保证 $2 \leq n \leq 10^4$ 对于 $50\%$ 的数据,保证 $ 2 \leq n \leq 10^7$ 对于 $100\%$ 的数据, 保证 $ 2 \leq n \leq 10^{12}$ 所有数据满足 $1 \leq T \leq 5$