#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define	I inline
using namespace std;

const int V = 1000100;
const int N = 150010;
const int B = 11000;
struct node {
	int l,m,r,v;
	node(int ll=0,int mm=0,int rr=0,int vv=0) {
		l=ll; m=mm; r=rr; v=vv;
	}
}cg[N*410];
struct Query {
	int l,r,id;
}b[N];
int n,q,a[N],cnt,bcnt,c[N];
int mx[B];
int nl[N],nr[N],bel[N],ans[N];
vector<int> ps[V];

I void build() {
	int sq=sqrt(n); bcnt=sq;
	for(int i=1;i<=sq;++i) {
		nl[i]=(i-1)*sq+1; nr[i]=i*sq;
	}
	if(nr[bcnt]!=n) {
		bcnt++;
		nl[bcnt]=nr[bcnt-1]+1;
		nr[bcnt]=n;
	}
	for(int i=1;i<=bcnt;++i)
		for(int j=nl[i];j<=nr[i];++j)
			bel[j]=i;
}
I void change(int ps,int v) { //cout<<"cg"<<endl;
	c[ps]=max(c[ps],v);
	mx[bel[ps]]=max(mx[bel[ps]],c[ps]);
}
I int query(int l) {
	int id=bel[l],ret=0;
	for(int i=1;i<id;++i) ret=max(ret,mx[i]);
	for(int i=nl[id];i<=l;++i) ret=max(ret,c[i]);
	return ret;
}
I bool cmp(Query q1,Query q2) {
	return q1.l>q2.l;
}
I bool cmp2(node n1,node n2) {
	return n1.l>n2.l;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=q;++i) {
		b[i].id=i;
		cin>>b[i].l>>b[i].r;
	}
	for(int i=1;i<=n;++i) {
		int sq=sqrt(a[i]);
		for(int j=1;j<=sq;++j) {
			if(a[i]%j==0) {
				ps[j].push_back(i);
				if(j*j!=a[i]) {
					ps[a[i]/j].push_back(i);
				}
			}
		}
	}	//cout<<"LLL"<<endl;

	for(int i=1;i<=1000000;++i) { //cout<<i<<endl;
		int p=0,sz=int(ps[i].size()-2),r=ps[i].size()-1;
		//mk.clear(); mkid.clear();
		for(int j=sz;j>=0;--j) {
			int l=ps[i][j],mid=ps[i][j+1];
			while(r&&ps[i][r-1]-mid>=mid-l) r--;
			if(ps[i][r]-mid>=mid-l) {
				cg[++cnt]=node(l,mid,ps[i][r],i);
			}
		}
		
	}

	build();
	sort(cg+1,cg+1+cnt,cmp2);
	sort(b+1,b+1+q,cmp);
	
	int j=1;
	for(int i=1;i<=q;++i) {
		while(j<=cnt&&cg[j].l>=b[i].l) {
			change(cg[j].r,cg[j].v);
			j++;
		}
		ans[b[i].id]=query(b[i].r);
	}
	for(int i=1;i<=q;++i) cout<<ans[i]<<endl;
}