#include<bits/stdc++.h>
using namespace std;
const int N=150005;
const int M=1000005;
int n,q;
int a[N];
int lst[M];
map<int,int>nxt[N];
vector<pair<int,int>>seg[N];
vector<pair<int,int>>query[N];
int ans[N];
struct Segment_Tree
{
    #define ls i*2
    #define rs i*2+1
    struct Node
    {
        int l,r;
        int mx;
    }tree[N*4];
    void push_up(int i)
    {
        tree[i].mx=max(tree[ls].mx,tree[rs].mx);
        return;
    }
    void build(int i,int l,int r)
    {
        tree[i].l=l,tree[i].r=r;
        if(l==r)
        {
            tree[i].mx=1;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(i);
        return;
    }
    void modify(int i,int u,int v)
    {
        if(tree[i].l==tree[i].r)
        {
            tree[i].mx=max(tree[i].mx,v);
            return;
        }
        if(u<=tree[ls].r) modify(ls,u,v);
        else modify(rs,u,v);
        push_up(i);
        return;
    }
    int query(int i,int ql,int qr)
    {
        if(ql<=tree[i].l&&tree[i].r<=qr) return tree[i].mx;
        int res=0;
        if(ql<=tree[ls].r) res=max(res,query(ls,ql,qr));
        if(qr>=tree[rs].l) res=max(res,query(rs,ql,qr));
        return res;
    }
}T;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=n;i>=1;i--)
    {
        nxt[i]=nxt[i+1];
        for(int j=1;j*j<=a[i];j++)
            if(a[i]%j==0) nxt[i][j]=nxt[i][a[i]/j]=i;
    }
    for(int j=1;j<=n;j++)
    {
        auto calc=[&](int g)
        {
            if(g==1) return;
            int i=lst[g];
            if(i<1) return;
            if(!nxt[j+j-i].count(g)) return;
            int k=nxt[j+j-i][g];
            seg[k].emplace_back(i,g);
            return;
        };
        for(int g=1;g*g<=a[j];g++)
            if(a[j]%g==0)
            {
                calc(g);
                if(g*g!=a[j]) calc(a[j]/g);
            }
        for(int g=1;g*g<=a[j];g++)
            if(a[j]%g==0) lst[g]=lst[a[j]/g]=j;
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        query[r].emplace_back(l,i);
    }
    T.build(1,1,n);
    for(int r=1;r<=n;r++)
    {
        for(auto &[i,g]:seg[r])
            T.modify(1,i,g);
        for(auto &[l,id]:query[r])
            ans[id]=T.query(1,l,r);
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
    return 0;
}