#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pr;

const int MAXN=1.5e5,MAXQ=1e5,MAXA=1e6,S=387;

int n,q,ans[MAXQ+5];
vector<int> fac[MAXA+5],loc[MAXA+5];
vector<pr> buc[MAXN+5],Q[MAXA+5],ope[MAXN+5];
vector<pr> qry[MAXN+5];

inline void Init()
{
    for(int i=1;i<=MAXA;i++)
        for(int j=i;j<=MAXA;j+=i)
            fac[j].push_back(i);
}

int maxn[MAXN+5],Maxn[S+5],Bloc[MAXN+5];
inline void Modify(int x,int v) {maxn[x]=max(maxn[x],v),Maxn[Bloc[x]]=max(Maxn[Bloc[x]],v);}
inline int GetMax(int L,int R)
{
	int res=0;
	for(int i=Bloc[L];i<Bloc[R];i++) res=max(res,Maxn[i]);
	for(int i=(Bloc[R]-1)*S+1;i<=R;i++) res=max(res,maxn[i]);
	return res;
}

int main()
{
    Init();
    scanf("%d %d",&n,&q);
    for(int i=1,A;i<=n;i++)
	{
		scanf("%d",&A);
		for(int j=0;j<fac[A].size();j++) loc[fac[A][j]].push_back(i);
	}
	for(int i=1;i<=MAXA;i++)
		for(int j=0;j+1<loc[i].size();j++)
			if(2*loc[i][j+1]-loc[i][j]<=n) buc[2*loc[i][j+1]-loc[i][j]].push_back(make_pair(loc[i][j],i));
	for(int i=1;i<=n;i++)
		for(int j=0;j<buc[i].size();j++)
			Q[buc[i][j].second].push_back(make_pair(buc[i][j].first,i));
	for(int i=1;i<=MAXA;i++)
		for(int j=0,k=0;j<Q[i].size();j++)
		{
			while(k<loc[i].size() && loc[i][k]<Q[i][j].second) ++k;
			if(k<loc[i].size()) ope[Q[i][j].first].push_back(make_pair(loc[i][k],i));
		}
	for(int i=1,L,R;i<=q;i++) scanf("%d %d",&L,&R),qry[L].push_back(make_pair(R,i));
	for(int i=1,L=1,R;L<=n;i++,L=R+1)
	{
		R=min(L+S-1,n);
		for(int j=L;j<=R;j++) Bloc[j]=i;
	}
	for(int i=n;i;i--)
	{
		for(int j=0;j<ope[i].size();j++) Modify(ope[i][j].first,ope[i][j].second);
		for(int j=0;j<qry[i].size();j++) ans[qry[i][j].second]=GetMax(i,qry[i][j].first);
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}