#include<bits/stdc++.h>
using namespace std;
constexpr int V=1000010;
int n,m,a[150010],ans[100010];
vector<int>divisor[1000010],pos[1000010];
struct Q_{int l,i;};
vector<Q_>q[150010];
vector<pair<int,int>>pr[150010];
namespace ds{
int mx[150010];
inline void ins(int p,int v){
   for(p=n-p+1;p<=n;p+=p&-p)mx[p]=max(mx[p],v);
}
inline int ask(int p){
   int res=0;
   for(p=n-p+1;p;p-=p&-p)res=max(res,mx[p]);
   return res;
}
}
int main(){
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)scanf("%d",&a[i]);
   for(int i=1,l,r;i<=m;i++){
      scanf("%d%d",&l,&r);
      q[r].push_back({l,i});
   }
   for(int i=1;i<=V;i++)for(int j=i;j<=V;j+=i)divisor[j].push_back(i);
   for(int i=1;i<=n;i++)for(int d:divisor[a[i]])pos[d].push_back(i);
   for(int i=1;i<=V;i++){
      for(int j=1;j<pos[i].size();j++){
         auto it=lower_bound(begin(pos[i]),end(pos[i]),pos[i][j]+pos[i][j]-pos[i][j-1]);
         if(it!=end(pos[i]))pr[*it].emplace_back(pos[i][j-1],i);
      }
   }
   for(int i=1;i<=n;i++){
      for(auto X:pr[i])ds::ins(X.first,X.second);
      for(Q_ x:q[i])ans[x.i]=ds::ask(x.l);
   }
   for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
   return 0;
}