代码打印

#include <bits/stdc++.h>
#define int long long
using namespace std;
const signed mod=998244353;
int b[1005],c[1005],f[1005][32];
int power(int n,int p)
{
	if(p==0)
	{
		return 1;
	}
	int tmp=power(n,p/2);
	if(p%2==0)
	{
		return tmp*tmp%mod;
	}
	return tmp*tmp%mod*n%mod;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,q;
		cin>>n>>q;
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
			c[i]=0;
			for(int j=2;j*j<=b[i];j++)
			{
				while(b[i]%j==0)
				{
					b[i]/=j;
					c[i]++;
				}
			}
			if(b[i]>1)
			{
				c[i]++;
			}
		}
		for(int i=1;i<=q;i++)
		{
			int l,r;
			cin>>l>>r;
			for(int j=0;j<32;j++)
			{
				f[l-1][j]=0;
			}
			f[l-1][0]=1;
			for(int j=l;j<=r;j++)
			{
				for(int k=0;k<32;k++)
				{
					f[j][k]=(f[j-1][k]+f[j-1][k^c[j]])%mod;
				}
			}
			cout<<((power(2,r-l+1)-1-f[r][1])%mod+mod)%mod<<"\n";
		}
	}
	return 0;
}
/*
1
8 13
1 1 4 16 2 8 3 7
1 2
1 5
5 6
2 5
1 8
2 7
3 8
6 8
5 8
3 6
1 1
3 3
5 5
*/