#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int B=1e9) {
	return (unsigned long long)rng() % B;
}
const int maxn=1.5e5+10;
struct tree{
    int c[maxn];
    int n;
    void set_n(int _n){
        n=_n;
        for(int i=1;i<=n;i++)c[i]=0;
    }
    int lowbit(int x){
        return x&(-x);
    }
    void update(int x,int k){
        while(x<=n){
            c[x]=max(c[x],k);
            x+=lowbit(x);
        }
    }
    int getsum(int x){
        int res=0;
        while(x>0){
            res=max(res,c[x]);
            x-=lowbit(x);
        }
        return res;
    }
}tri;
// vector<int>pr;
// void init()
// {
//     int N=1e6;
//     vector<int> vis(N+1);
//     for(int i=2;i<=N;i++)if(!vis[i]){
//         pr.push_back(i);
//         for(int j=i*2;j<=N;j++)vis[j]=1;
//     }
// }
const int N=1e6;
const int M=3e2;
vector<int> ve[N+1];
vector<int> ve2[M+1];
vector<pair<int,int>> ma[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    // int n=1.5e5,q=1e5;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        // a[i]=2*3*5*7*11*13*15;
        for(int j=1;j<=M;j++)if(a[i]%j==0)ve[j].push_back(i);
        if(a[i]>M)ve[a[i]].push_back(i);
    }
    // for(int i=1;i<=10;i++){for(auto it:ve2[i])cout<<it<<" ";;;cout<<endl;}
    for(int i=1;i<=M;i++){
        vector<int>& all=ve[i];
        for(int j=0;j+2<all.size();j++){
            int x=all[j],y=all[j+1];
            auto it=lower_bound(all.begin(),all.end(),y+y-x);
            if(it!=all.end()){
                ma[x].emplace_back(*it,i);
                // cout<<x<<" "<<*it<<" "<<i<<endl;
            }
        }
    }
    for(int i=M+1;i<=N;i++){
        vector<int>all;
        int cnt=0;
        for(int j=i;j<=N;j+=i)if(!ve[j].empty()){
            for(auto &it:ve[j])all.push_back(it);
            cnt++;
        }
        // if(cnt==1&&ve[i].empty())continue;
        sort(all.begin(),all.end());
        for(int j=0;j+2<all.size();j++){
            int x=all[j],y=all[j+1];
            auto it=lower_bound(all.begin(),all.end(),y+y-x);
            if(it!=all.end()){
                ma[x].emplace_back(*it,i);
                // cout<<x<<" "<<*it<<" "<<i<<endl;
            }
        }
    }
    vector<tuple<int,int,int>> query(q);
    for(int i=0;i<q;i++){
        int l,r;
        // l=rnd()%n+1,r=rnd()%n+1;if(l>r)swap(l,r);
        cin>>l>>r;
        query[i]=make_tuple(l,r,i);
    }
    sort(query.begin(),query.end());
    reverse(query.begin(),query.end());
    int now=n;
    tri.set_n(n);
    vector<int> ans(q);
    for(auto &[l,r,id]:query){
        while(now>=l){
            for(auto &[rr,w]:ma[now])tri.update(rr,w);
            now--;
        }
        if(r-l<=1){ans[id]=0;continue;}
        ans[id]=tri.getsum(r);
        // for(int i=M;i>ans[id];i--){
        //     auto it1=lower_bound(ve2[i].begin(),ve2[i].end(),l);
        //     auto it2=upper_bound(ve2[i].begin(),ve2[i].end(),r);
        //     if(it2-it1>=3)ans[id]=i;
        // }
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
    return 0;
}