题目描述
杜老师可是要打 +∞ 年 World Final 的男人,虽然规则不允许,但是可以改啊!
但是今年 WF 跟 THUSC 的时间这么近,所以他造了一个 idea 就扔下不管了……
给定 L,R,求从 L 到 R 的这 R−L+1 个数中能选出多少个不同的子集,满足子集中所有的数的乘积是一个完全平方数。特别地,空集也算一种选法,定义其乘积为 1。
由于杜老师忙于跟陈老师和鏼老师一起打 ACM 竞赛,所以,你能帮帮杜老师写写标算吗?
输入格式
从标准输入读入数据。
每个测试点包含多组测试数据。
输入第一行包含一个正整数 T(1≤T≤100),表示测试数据组数。
接下来 T 行,第 i+1 行两个正整数 Li,Ri 表示第 i 组测试数据的 L,R,保证 1≤Li≤Ri≤107。
输出格式
输出到标准输出。
输出 T 行,每行一个非负整数,表示一共可以选出多少个满足条件的子集,答案对 998244353 取模。
样例 1
3
1 8
12 24
1 1000000
16
16
947158782
对于 L=1,R=8,对应的 16 种选法为:
- 空集
- 4
- 3,6,8
- 3,4,6,8
- 2,8
- 2,4,8
- 2,3,6
- 2,3,4,6
- 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
6
3761870 4957871
2262774 4279409
3027437 5896884
3884310 5021632
3373244 5464739
5063504 5368121
953622420
551347610
583188135
582472626
190680894
268824018
数据范围与提示
测试点 |
Ri |
T |
∑i=1TRi−Li+1 |
特殊约束 |
1, 2 |
≤30 |
≤10 |
≤103 |
无特殊约束 |
3 |
≤102 |
保证答案不超过 5×106 |
4 |
无特殊约束 |
5, 6 |
≤103 |
Ri−Li≤22 |
7, 8 |
保证答案不超过 2×106 |
9, 10 |
≤5,000 |
无特殊约束 |
11, 12 |
≤106 |
≤107 |
Ri−Li≥999,990 |
13, 14 |
无特殊约束 |
15 |
≤107 |
≤100 |
16 |
≤2×107 |
17 |
≤3×107 |
18 |
≤4×107 |
19 |
≤5×107 |
20 |
≤6×107 |