#include <bits/stdc++.h>
using namespace std;
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]=1;
    }
    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=1;
        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;
vector<int> ve[N+1];
map<int,int> ma[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],ve[a[i]].push_back(i);
    for(int i=2;i<=N;i++){
        vector<int>all;
        for(int j=i;j<=N;j+=i){
            for(auto it:ve[j])all.push_back(it);
        }
        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][*it]=i;
                // cout<<"x="<<x<<" y="<<*it<<" w="<<i<<endl;
            }
        }
    }
    vector<tuple<int,int,int>> query(q);
    for(int i=0;i<q;i++){
        int 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--;
        }
        ans[id]=tri.getsum(r);
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
    return 0;
}