#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF  = 0x3f3f3f3f;
const ll INFll  = 0x3f3f3f3f3f3f3f3f;
#define endl "\n" 
#define x first
#define y second

vector<vector<int>>adj(N);

int a[N];

struct Node{
    int l, r, w;
}query[N];
int ans[N];

struct gfseg { // 区间最值
    int a[N], _n;
    struct Node {
        int l, r;
        int max;
    }tr[N];

    void pushup(int u) {
        tr[u].max = max(tr[u << 1].max, tr[u << 1 | 1].max);
    }

    void build(int u, int l, int r) {
 
        if(l == r) {
            tr[u] = {l, r, a[l]};
            return;
        }
        int mid = l + r >> 1;
        tr[u] = {l, r, -INF};
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }

    void init(vector<int> _a) {
        _n = _a.size();
        for(int i = 1; i <= _n; i ++) {
            a[i] = _a[i - 1];
        } 
        build(1, 1, _n);
    }

    void modify(int u, int x, int y) {
        if(tr[u].l == tr[u].r && tr[u].l == x) {
            tr[u].max = max(tr[u].max, y);
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, y);
        if(x >  mid) modify(u << 1 | 1, x, y);
        pushup(u);
    }


    int querymax(int u, int l, int r) {
        if(l <= tr[u].l && tr[u].r <= r) {
            return tr[u].max;
        }

        int res = -INF;
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) res = max(querymax(u << 1, l,  r), res);
        if(r >  mid) res = max(querymax(u << 1 | 1, l,  r), res);
        return res;
    }

    void debug() {
        for(int i = 1; i <= _n; i ++)
        cout << querymax(1, i, i) << " "; cout <<  endl;
    }
}tr;



void solve()
{
    
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        // a[i] = rand();
        int x = a[i];
        for(int j = 1; j * j <= x; j ++) {
            if(x % j == 0) {
                adj[j].push_back(i);
                if(j * j != x) 
                    adj[x/j].push_back(i);
            }
        }
    }
    vector<Node> no;
    for(int i = 1; i < N; i ++) {
        int l = 0, r = 0;
        for(int l = 0; l < adj[i].size(); l ++) {
            while(r <= l + 1 && r < adj[i].size()) r ++;

            while(r < adj[i].size()) {
                if(r < adj[i].size() && adj[i][l + 1] - adj[i][l] <= adj[i][r] - adj[i][l + 1]) {
                    no.push_back({adj[i][l], adj[i][r], i});
                    break;
                }
                else r ++;
            }


        }
    }

    // cout << no.size() << endl;
    // for(auto [l, r, w]:no) cout << l << " " << r << " " << w << endl;

    vector<int>T; for(int i = 1; i <= n + 10; i ++) T.push_back(0); tr.init(T);

    for(int i = 0; i < q; i ++) {
        cin >> query[i].l >> query[i].r; query[i].w = i;
    }

    sort(query , query + q, [&](Node a, Node b){
        return a.l > b.l;
    });

    sort(no.begin(), no.end(), [&](Node a, Node b){
        if(a.l == b.l) return a.w > b.w;
        return a.l > b.l;
    });

    vector<int>mx (n + 10, 0);
    int i = 0, j = 0;
    for(int L = n; L >= 0; L --) {
        // cout << L  << ":\n";
        while(i < no.size() && no[i].l >= L) {
            // cout << no[i].l << " " << no[i].r << " " << no[i].w << endl;
            if(mx[no[i].r] < no[i].w) {
                tr.modify(1, no[i].r, no[i].w);
                mx[no[i].r] = no[i].w;
            }
            i ++;
        }

        while(j < q && query[j].l >= L) {
            ans[query[j].w] = tr.querymax(1,1,query[j].r);
            j ++;
        }
    }
    // tr.debug();
    // cout << i << " " << j << endl;

    for(int i = 0; i < q; i ++) cout << ans[i] << endl;


}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cout << setprecision(11) << fixed;
    int t;t=1;
    //cin>>t;
    for(int i=1;i<=t;i++){
        //printf("Case %d: ",i);
        solve();
    }
}