#include <bits/stdc++.h>

using namespace std;
using ii = pair <int, int>;

const int N = 1e4 + 1;
const int S = 300;

int n, q, Max[N];
vector <int> dv[N], pos[N];
int ans[N], lqr[N], rqr[N], ord[N];
int id[N], lbl[S * 5], rbl[S * 5], nbl, used[N];
ii f[N], g[S * 5];

void rebuild(int bl){
    for (int i = lbl[bl]; i <= rbl[bl]; ++ i){
        if (i == lbl[bl]) f[i] = {0, 0};
        else f[i] = f[i - 1];
        int v = 0;
        if (!used[i]) v = rqr[ord[i]];
        f[i] = max(f[i], {v, i});
    }
    for (int sf = bl; sf <= nbl; ++ sf)
        g[sf] = max(g[sf - 1], f[rbl[sf]]);
}

ii get(int p){
    p = Max[p];
    return max(g[id[p] - 1], f[p]);
}

void process(){
    cin >> n >> q;
    for (int i = 1; i < N; ++ i){
        for (int j = i; j < N; j += i)
            dv[j].push_back(i);
    }

    for (int i = 1; i <= n; ++ i){
        int a; cin >> a;
        for (int u : dv[a])
            pos[u].push_back(i);
    }

    for (int i = 1; i <= q; ++ i){
        cin >> lqr[i] >> rqr[i];
        ord[i] = i;
    }

    sort(ord + 1, ord + q + 1, [&](int u, int v){
        return lqr[u] < lqr[v];
    });

    int ptr = 0;
    for (int i = 1; i <= n; ++ i){
        while (ptr < q && i >= lqr[ord[ptr + 1]]) ptr ++;
        Max[i] = ptr;
    }

    nbl = q / S + 1;
    for (int i = 1; i <= q; ++ i){
        id[i] = i / S + 1;
        if (!lbl[id[i]]) lbl[id[i]] = i;
        rbl[id[i]] = i;
    }
    for (int bl = 1; bl <= nbl; ++ bl) rebuild(bl);


    for (int gcd = N - 1; gcd >= 1; -- gcd){
        int num = pos[gcd].size();
        if (num < 3) continue;
        vector <int> pref(num - 1), ok(num - 1);
        pref[num - 2] = 1e9;
        for (int i = num - 3; i >= 0; -- i){
            int v = pos[gcd][i + 1] * 2 - pos[gcd][i];
            pref[i] = pref[i + 1];
            if (v < pref[i + 1]){
                ok[i] = 1;
                pref[i] = v;
            }
        }
        int ptr = 0;
        for (int i = 0; i < num - 2; ++ i) if (ok[i]){
            while (ptr < num && pos[gcd][i + 1] - pos[gcd][i] > pos[gcd][ptr] - pos[gcd][i + 1]) ptr ++;
            if (ptr == num) break;
            int sl = pos[gcd][i];
            int sr = pos[gcd][ptr];
            while (true){
                ii tmp = get(sl);
                if (tmp.first < sr) break;
                ans[ord[tmp.second]] = gcd;
                used[tmp.second] = 1;
                rebuild(id[tmp.second]);
            }
        }
    }

    for (int i = 1; i <= q; ++ i) cout << ans[i] << "\n";
}

int main(){
    freopen("10.inp", "r", stdin);
    freopen("10.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    process();
    return 0;
}