#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define N 100000
#define M 2000000
#define K 1200
#define mod 998244353
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
};
int n,m,sz,sz2,Base,a[N+1],w[N+1],block[N+1],block2[N+1],tong[N+1],length,l[N+1],r[N+1],ans[N+1],cnt[K+1],res[N+1][K+1],ds[N+1],ds2[N+1],ds3[N+1],ft[N+1],ft2[N+1];
bool nprime[N+1];
vector<int>p[N+1];
vector<int>v[N+1];
vector<int>delta[N+1];
vector<reads>vs[N+1];
vector<reads>qt[N+1];
vector<reads>st[N+1];
void adder(int x,int d)
{
	for (int i=ft[block2[x]];i<=x;++i) ds[i]=1ll*ds[i]*d%mod;
	for (int i=ft2[block[x]];i<=block2[x]-1;++i) ds2[i]=1ll*ds2[i]*d%mod;
	for (int i=1;i<=block[x]-1;++i) ds3[i]=1ll*ds3[i]*d%mod;
	return;
}
int query(int x)
{
	return 1ll*ds[x]*ds2[block2[x]]%mod*ds3[block[x]]%mod;
}
int main()
{
	int x,d,rst;
	n=read(),m=read(),sz=max((int)(pow(n,2.0/3)),1),sz2=max((int)(pow(n,1.0/3)),1);
	for (int i=1;i<=n;++i)
	{
		block[i]=(i-1)/sz+1;
		for (int j=(i-1)*sz+1;j<=min(i*sz,n);++j) block2[j]=block2[(i-1)*sz]+(j-(i-1)*sz-1)/sz2+1;
	}
	for (int i=n;i>=1;--i) ft[block2[i]]=i,ft2[block[i]]=block2[i];
	for (int i=2;i<=N;++i)
		if (!nprime[i])
		{
			w[i]=i;
			for (int j=(i<<1);j<=N;j+=i) w[j]=i,nprime[j]=1;
		}
	for (int i=1;i<=n;++i)
	{
		x=a[i]=read(),rst=1,d=0,ds[i]=ds2[i]=ds3[i]=1;
		while (x!=1)
		{
			if (w[x]!=d) rst=1;
			rst*=w[x],d=w[x],x/=w[x],p[rst].push_back(i);
		}
	}
	for (int i=1;i<=N;++i) Base+=p[i].size();
	Base=sqrt(Base);
	for (int i=1;i<=N;++i)
		if (!p[i].empty())
		{
			if (p[i].size()<=Base)
			{
				for (int j=0;j<p[i].size();++j) qt[p[i][j]].push_back((reads){i,j});
			}
			else
			{
				tong[++length]=i,delta[length].resize(p[i].size()+1),delta[length][0]=1;
				for (int j=1;j<delta[length].size();++j) delta[length][j]=1ll*delta[length][j-1]*delta[length][j-1]%mod*w[i]%mod;
				for (int j=0;j<p[i].size();++j) v[p[i][j]].push_back(length);
			}
		}
	for (int i=1;i<=m;++i) l[i]=read(),r[i]=read(),ans[i]=1,vs[l[i]-1].push_back((reads){i,-1}),vs[r[i]].push_back((reads){i,1}),st[r[i]].push_back((reads){i,l[i]});
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<v[i].size();++j) cnt[v[i][j]]++;
		for (int j=0;j<vs[i].size();++j)
			for (int k=1;k<=length;++k)
				res[vs[i][j].num][k]+=cnt[k]*vs[i][j].data;
	}
	for (int i=1;i<=m;++i)
		for (int j=1;j<=length;++j)
			ans[i]=1ll*ans[i]*delta[j][res[i][j]]%mod;
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<qt[i].size();++j)
		{
			adder(i,w[qt[i][j].num]);
			for (int k=qt[i][j].data-1,tres=w[qt[i][j].num];k>=0;--k,tres=1ll*tres*tres%mod) adder(p[qt[i][j].num][k],tres);
		}
		for (int j=0;j<st[i].size();++j) ans[st[i][j].num]=1ll*ans[st[i][j].num]*query(st[i][j].data)%mod;
	}
	for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}