#include<bits/stdc++.h>
using namespace std;
const int N=15e4+5,V=1e6+5;
using pii=pair<int,int>;
int n,q,a[N],pr[V];
vector<pii> qr[N],mf[N],vc[N];
int d[N<<2],ans[N];
void build(int l,int r,int k)
{
    if(l==r)return d[k]=0,void();
    int mid=(l+r)>>1;
    build(l,mid,k<<1),build(mid+1,r,k<<1|1);
    d[k]=max(d[k<<1],d[k<<1|1]);
}void modify(int p,int v,int l,int r,int k)
{
    if(l==r)return d[k]=max(v,d[k]),void();
    int mid=(l+r)>>1;
    if(p<=mid)modify(p,v,l,mid,k<<1);
    else modify(p,v,mid+1,r,k<<1|1);
    d[k]=max(d[k<<1],d[k<<1|1]);
}int query(int a,int b,int l,int r,int k)
{
    if(a<=l&&r<=b)return d[k];
    int mid=(l+r)>>1,ans=1;
    if(a<=mid)ans=max(ans,query(a,b,l,mid,k<<1));
    if(mid+1<=b)ans=max(ans,query(a,b,mid+1,r,k<<1|1));
    return ans;
}int main()
{
    ios::sync_with_stdio(0);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++)
    {
        int l,r;cin>>l>>r;
        qr[r].push_back({l,i});
    }for(int i=1;i<=n;i++)
    {
        for(int j=1;j*j<=a[i];j++)
        {
            if(a[i]%j)continue;int p=pr[j];
            if(p&&2*i-p<=n)vc[2*i-p].push_back({p,j});
            pr[j]=i;if(j*j==a[i])break;
            p=pr[a[i]/j];if(p&&2*i-p<=n)
            vc[2*i-p].push_back({p,a[i]/j});
            pr[a[i]/j]=i;
        }
    }for(int i=1;i<V;i++)pr[i]=0;
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j*j<=a[i];j++)
        if(a[i]%j==0)
        pr[j]=pr[a[i]/j]=i;
        for(auto el:vc[i])
        {
            int l=el.first;
            int vl=el.second;if(pr[vl])
            mf[pr[vl]].push_back({l,vl});
        }
    }for(int r=1;r<=n;r++)
    {
        for(auto el:mf[r])
        {
            int l=el.first;
            int vl=el.second;
            modify(l,vl,1,n,1);
        }for(auto el:qr[r])
        {
            int l=el.first;
            int id=el.second;
            ans[id]=query(l,r,1,n,1);
        }
    }for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
    return 0;
}