#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int,int>;
const int maxn = 1e6+100;


vector<int> factor[maxn];

void Sieve(){
    for(int i=1;i<maxn;++i){
        for(int j=i;j<maxn;j+=i) factor[j].push_back(i);
    }
}

int n,Q;
int a[maxn];
vector<pii> qry[maxn];
int ans[maxn];

vector<int> pos[maxn];
int tagv[maxn<<2],maxv[maxn<<2];


void pushtag(int o,int val){
    maxv[o] = max(maxv[o],val);
    tagv[o] = max(tagv[o],val);
}
void pushdown(int o){
    pushtag(o<<1,tagv[o]);
    pushtag(o<<1|1,tagv[o]);
    tagv[o] = 0;
}
void seg_upd(int o,int l,int r,int ql,int qr,int val){
    if(ql<=l && r<=qr){
        pushtag(o,val);
        return ;
    }
    pushdown(o);
    int mid=l+r>>1;
    if(ql<=mid) seg_upd(o<<1,l,mid,ql,qr,val);
    if(qr>mid) seg_upd(o<<1|1,mid+1,r,ql,qr,val);
    maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);
}
int seg_max(int o,int l,int r,int q){
    if(l==r) return maxv[o];
    pushdown(o);
    int mid= l+r>>1,res=0;
    if(q<=mid) return seg_max(o<<1,l,mid,q);
    else return seg_max(o<<1|1,mid+1,r,q);
    
}
main(){
    srand(time(0));
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(0);
    // Sieve();
    cin>>n>>Q;
    for(int i=1;i<=n;++i){
        cin >> a[i];
        if(factor[a[i]].empty())for(int d=1;d*d<=a[i];++d){
            if(a[i]%d == 0){
                factor[a[i]].push_back(d);
                if(d*d!=a[i]) factor[a[i]].push_back(a[i]/d);
            }
        }
        // a[i] = rand()+1;
    }
    for(int i=1;i<=Q;++i){
        int l,r;
        cin>>l>>r;
        // l=rand()%n+1,r=rand()%n+1; if(l>r) swap(l,r);
        qry[r].emplace_back(l,i);
    }
    
    // for(int i=1;i<maxn;++i) pos[i].push_back(0);
    for(int i=1;i<=n;++i){
        for(int fac:factor[a[i]]){
            if(pos[fac].empty()) pos[fac].push_back(0);
            pos[fac].push_back(i);
        }
    }

    for(int r=1;r<=n;++r){
        for(int fac:factor[a[r]]){
            // auto it = --pos[fac].lower_bound(r);
            auto it = lower_bound(pos[fac].begin(),pos[fac].end(),r) - 1;
            while(it!=pos[fac].begin()){
                auto ne = --it; ++ it;
                if(ne == pos[fac].begin()) break;
                if(*it - *ne <= r - *it){
                    seg_upd(1,1,n,1,*ne,fac);
                    break;
                }
                --it;
            }
        }
        for(auto[l,idx]:qry[r]){
            ans[idx]=seg_max(1,1,n,l);
        }
    }

    for(int i=1;i<=Q;++i) cout<<ans[i]<<'\n';
    // cerr<<"!!!\n";
}