[THUSCH2017] 杜老师
题目描述
杜老师可是要打 $+∞$ 年 World Final 的男人,虽然规则不允许,但是可以改啊!
但是今年 WF 跟 THUSC 的时间这么近,所以他造了一个 idea 就扔下不管了……
给定 $L,R$,求从 $L$ 到 $R$ 的这 $R-L+1$ 个数中能选出多少个不同的子集,满足子集中所有的数的乘积是一个完全平方数。特别地,空集也算一种选法,定义其乘积为 $1$。
由于杜老师忙于跟陈老师和鏼老师一起打 ACM 竞赛,所以,你能帮帮杜老师写写标算吗?
输入输出格式
输入格式
从标准输入读入数据。
每个测试点包含多组测试数据。
输入第一行包含一个正整数 $T$($1\le T\le 100$),表示测试数据组数。
接下来 $T$ 行,第 $i+1$ 行两个正整数 $L_i,R_i$ 表示第 $i$ 组测试数据的 $L,R$,保证 $\le L_i\le R_i\le10^7$。
输出格式
输出到标准输出。
输出 $T$ 行,每行一个非负整数,表示一共可以选出多少个满足条件的子集,答案对 $998244353$ 取模。
输入输出样例
输入样例 #1
3
1 8
12 24
1 1000000
输出样例 #1
16
16
947158782
输入样例 #2
6
3761870 4957871
2262774 4279409
3027437 5896884
3884310 5021632
3373244 5464739
5063504 5368121
输出样例 #2
953622420
551347610
583188135
582472626
190680894
268824018
说明
对于 $L=1,R=8$,对应的 $16$ 种选法为:
1. 空集
1. $4$
1. $3,6,8$
1. $3,4,6,8$
1. $2,8$
1. $2,4,8$
1. $2,3,6$
1. $2,3,4,6$
1. $1$
1. $1,4$
1. $1,3,6,8$
1. $1,3,4,6,8$
1. $1,2,8$
1. $1,2,4,8$
1. $1,2,3,6$
1. $1,2,3,4,6$
| 测试点 $\operatorname*{Id}$ | $R_i\le$ | $T\le$ | $\sum R_i-L_i+1\le$ | 特殊约束 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| 1~2 | $30$ | $10$ | $10^3$ | 无特殊约束 |
| 3 | $100$ | $10$ | $10^3$ | 保证答案不超过 $5\times 10^6$ |
| 4 | $100$ | $10$ | $10^3$ | 无特殊约束 |
| 5~6 | $10^3$ | $10$ | $10^3$ | $R-L\le22$ |
| 7~8 | $10^3$ | $10$ | $10^3$ | 保证答案不超过 $2\times 10^6$ |
| 9~10 | $10^3$ | $10$ | $5\times10^3$ | 无特殊约束 |
| 11~12 | $10^6$ | $10$ | $10^7$ | $R-L\ge999990$ |
| 13~14 | $10^6$ | $10$ | $10^7$ | 无特殊约束 |
| 15~20 | $10^7$ | $100$ | $(\operatorname*{Id}-14)\times 10^7$ | 无特殊约束 |