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

const int N=1e6+5;
int n,m,a[N],mx,ql[N],qr[N],ans[N];
vector<int> p[N],G[N];
struct Nod{int x,v;};
vector<Nod> op[N];
vector<int> Q[N];

namespace BIT{
  int tr[N];
  int lowbit(int i){return i&(-i);}
  void upd(int x,int v){for(int i=x;i<=n;i+=lowbit(i)) tr[i]=max(tr[i],v);}
  int qry(int x){
	int res=1;
	for(int i=x;i>=1;i-=lowbit(i)) res=max(res,tr[i]);
	return res;
  }
}
using namespace BIT;

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i],mx=max(mx,a[i]);

  for(int i=2;i<=mx;i++) for(int j=i;j<=mx;j+=i) p[j].pb(i);
  for(int i=1;i<=n;i++) for(auto j:p[a[i]]) G[j].pb(i);

  for(int i=2,sz;i<=mx;i++){
    sz=(int)G[i].size();

	for(int j=1;j<sz;j++){
	  int tmp=lower_bound(G[i].begin(),G[i].end(),2*G[i][j]-G[i][j-1])-G[i].begin();
	  if(tmp<sz) op[G[i][tmp]].pb({G[i][j-1],i});
	}
  }

  for(int i=1;i<=m;i++) cin>>ql[i]>>qr[i],ans[i]=1,Q[qr[i]].pb(i);

  for(int i=1;i<=n;i++){
	for(auto j:op[i]) upd(n-j.x+1,j.v);
	for(auto j:Q[i]) ans[j]=qry(n-ql[j]+1);
  }

  for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
  return 0;
}
/*
8 1
8 24 4 6 6 7 3 3
2 6
*/