先考虑最暴力的做法，一个数x，含有的质因子p的指数如果是奇数，那么在这一位视作1，答案相当于与选若干数，异或起来是0。
如果暴力建线性基，求出自由元的个数(s)，答案就是(2^s)。
这个大概能跑过(r<=1000)
考虑进一步的优化，对于那些(>sqrt n)的质因子，如果它出现，那么指数一定是1，并且一个数不会有两个及以上的这样的质因子。
那么线性基只维护(<=sqrt n)的质因子，对于(>sqrt n)的质因子，在外面就讨论好。
假如先遇到一个含有(p1>sqrt n)的，就让它停在线性基这一位上，不加入维护的那个线性基，后面再遇到含有p1的，就异或上之前它再加入线性基。
这样，线性基中的长度只有不到450个，这个能多跑2个点。
事实上，因为线性基的长度不大了，所以很容易加满，加满了就不加了，然后你发现你就能过了。
设一个阈值M，当(r-l>M)时，线性基一定会被填满。
(M)至少是(sqrt n)，应该再大一点以使线性基中不会冲突，取(M=2sqrt n)就行了。
当(r-l>M)时，自由元个数(s=r-l+1-[l,r]含有的不同质因子的个数)。
含有不同质因子的个数：枚举每个质数，看它有没有出现在这个区间内。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 998244353;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const int N = 1e7 + 5;
const int M = 450;
int n, sq, m;
int bz[N], p[N], p0, bp[N], mp[N], sp[N];
int T, l, r;
int us[N];
bitset<M> d[100005]; int d0;
bitset<M> a[M], b; int qa[N];
int ins() {
fd(i, m, 1) if(b[i]) {
if(qa[i]) {
b ^= a[i];
} else {
qa[i] = 1;
a[i] = b;
return 0;
}
}
return 1;
}
int add(int x) {
int t = mp[x];
if(t > sq) x /= t;
b.reset();
while(x > 1) {
int y = mp[x], c = 0;
while(x % y == 0) x /= y, c ^= 1;
b[bp[y]] = c;
}
if(t > sq) {
if(us[t]) {
b ^= d[us[t]];
} else {
d[++ d0] = b;
us[t] = d0;
return 0;
}
}
return ins();
}
void work(int l, int r) {
fo(i, 1, m) a[i].reset(), qa[i] = 0;
int s = 0;
fo(i, l, r) s += add(i);
fo(i, l, r) us[mp[i]] = 0; d0 = 0;
pp("%lld
", ksm(2, s));
}
int main() {
n = 1e7; sq = sqrt(n);
mp[1] = 1;
fo(i, 2, n) {
sp[i] = sp[i - 1] + !bz[i];
if(!bz[i]) {
mp[i] = i;
p[++ p0] = i;
bp[i] = p0;
}
for(int j = 1; i * p[j] <= n; j ++) {
int k = i * p[j]; bz[k] = 1;
mp[k] = mp[i];
if(i % p[j] == 0) break;
}
}
fo(i, 2, sq) if(!bz[i]) m = bp[i];
for(scanf("%d", &T); T; T --) {
scanf("%d %d", &l, &r);
if(r - l <= 7000) {
work(l, r);
} else {
int s = r - l + 1;
fo(i, 1, p0) {
if(p[i] > r) break;
if(r / p[i] != (l - 1) / p[i]) s --;
}
pp("%lld
", ksm(2, s));
}
}
}