题目描述

请问有多少对正整数 $a,b$，满足存在整数 $k \ge 2$ 使得对于任意正整数 $x$ 都有 $\sqrt[k]{ax+b}$ 不为最简根式，且 $1 \le a,b \le n$，输出答案对 $998244353$ 取模后的结果，多组数据。

注：形式化地，最简根式是指被开方数的指数与根指数互质、被开方数中不含开得尽方的因数或因式、被开方数不含分母的根式。更加通俗地，你可以认为最简根式就是不能被化简的根式。例如，$\sqrt{3}$，$\sqrt{10}$ 和 $\sqrt[3]{18}$ 都是最简根式，而 $\sqrt{4}$，$\sqrt{8}$ 和 $\sqrt[3]{24}$ 都不是最简根式，因为 $\sqrt{4}=2$，$\sqrt{8}=2\sqrt{2}$，$\sqrt[3]{24}=2\sqrt[3]{3}$。

输入格式

第一行一个整数 $T$ ，表示数据组数。对每组数据输入一行一个整数 $n$。

输出格式

对每组数据输出一行一个整数，表示答案对 $998244353$ 取模的值。

数据范围

对于 $10\%$ 的数据，$1 \le n \le 10$ 对于 $20\%$ 的数据，$1 \le n \le 1000$ 对于 $30\%$ 的数据，$1 \le n \le 10^{6}$ 对于 $40\%$ 的数据，$1 \le T \le 10,1 \le n \le 10^{12}$ 对于 $70\%$ 的数据，$1 \le T \le 2000,1 \le n \le 10^{12}$ 对于剩下 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 10^{18}$

输入样例 1

5
1
3
5
7
9

输出样例 1

0
0
1
1
5

输入样例 2

20
32
321
3216
32162
321625
3216253
32162532
321625321
3216253216
32162532162
321625321625
3216253216253
32162532162532
321625321625321
3216253216253216
32162532162532162
321625321625321625
555555555555555555
888888888888888888
999999999999999999

输出样例 2

74
7736
786247
78664873
880245839
185365181
653221597
822249331
541805958
444286604
738869083
881696988
131329235
550975081
278980712
253813702
952064402
805108919
787522701
84903137