#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int N=1e6+10,V=1e6;
int n,q,a[N],ans[N];
vector<int> G[N],ps[N];
vector<pair<int,int> >qr[N],qs[N];
int t[N];
#define lbt(x) (x&-x)
void add(int x,int k){for(;x<=n;x+=lbt(x)) t[x]=max(t[x],k);}
int ask(int x){int res=1;for(;x;x-=lbt(x)) res=max(res,t[x]);return res;}
int main(){
	rep(i,2,V) rep(j,1,V/i) G[i*j].push_back(i);
	scanf("%d%d",&n,&q);int l,r,x;rep(i,1,n){scanf("%d",&x);for(int y:G[x]) ps[y].push_back(i);}
	rep(x,2,V){
		if(ps[x].size()<2) continue;
		int j=0;rep(i,0,ps[x].size()-2){
			while(j<ps[x].size()&&ps[x][j]-ps[x][i+1]<ps[x][i+1]-ps[x][i]) ++j;
			if(j<ps[x].size()&&ps[x][j]-ps[x][i+1]>=ps[x][i+1]-ps[x][i]) qs[ps[x][i]].push_back({ps[x][j],x});
		}
	}
	rep(i,1,q){scanf("%d%d",&l,&r);if(r-l>=2) qr[l].push_back({r,i});}
	per(i,n,1){
		for(auto I:qs[i]) add(I.first,I.second);
		for(auto I:qr[i]) ans[I.second]=ask(I.first);
	}
	rep(i,1,q) printf("%d\n",ans[i]);
    return 0;
}