#P11481. [2023省队模拟]最简根式

    ID: 10629 传统题 6000ms 888MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-中国剩余定理莫比乌斯函数容斥原理交换求和顺序整除分块杜教筛线性筛一维前缀和阈值划分大小情况

[2023省队模拟]最简根式

题目描述

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

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

输入格式

第一行一个整数 TT ,表示数据组数。对每组数据输入一行一个整数 nn。

输出格式

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

数据范围

对于 10%10\% 的数据,1≤n≤101 \le n \le 10 对于 20%20\% 的数据,1≤n≤10001 \le n \le 1000 对于 30%30\% 的数据,1≤n≤1061 \le n \le 10^{6} 对于 40%40\% 的数据,1≤T≤10,1≤n≤10121 \le T \le 10,1 \le n \le 10^{12} 对于 70%70\% 的数据,1≤T≤2000,1≤n≤10121 \le T \le 2000,1 \le n \le 10^{12} 对于剩下 30%30\% 的数据,1≤T≤101 \le T \le 10,1≤n≤10181 \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