#include "bits/stdc++.h"

using namespace std;


class PQ {
public:
    priority_queue<int> pq;
    priority_queue<int> e;

    void emplace(int x) {
        pq.emplace(x);
    }

    void erase(int x) {
        e.emplace(x);
    }

    int top() {
        while (!e.empty() && e.top() == pq.top()) {
            e.pop(), pq.pop();
        }
        return pq.top();
    }

    bool empty() { return pq.size() == e.size(); }
};

class Set {
public:
    int n;
    vector<int> v;

    Set(int n) : n(n), v(n << 2) {};

    void push_up(int q) {
        v[q] = max(v[q << 1], v[q << 1 | 1]);
    }

    void modify(int q, int l, int r, int pos, int x) {
        if (l == r) {
            v[q] = x;
        } else {
            int mid = (l + r) / 2;
            if (mid >= pos) {
                modify(q << 1, l, mid, pos, x);
            } else {
                modify(q << 1 | 1, mid + 1, r, pos, x);
            }
            push_up(q);
        }
    }

    int query(int q, int l, int r, int L, int R) {

        if (l > r || l > R || r < L)return 0;
        if (L <= l && r <= R) {
//            cerr << l << " " << r << endl;
            return v[q];
        }
        int mid = (l + r) / 2;
        int res = 0;
        return max(query(q << 1, l, mid, L, R),
                   query(q << 1 | 1, mid + 1, r, L, R));
    }
};


void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<vector<int>> qq(1e6 + 1);
    vector<vector<int>> pre(n + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                qq[j].emplace_back(i);
                pre[i].emplace_back(j);
                if (a[i] / j != j) {
                    qq[a[i] / j].emplace_back(i);
                    pre[i].emplace_back(a[i] / j);
                }
            }
        }
    }
    auto lower = [&](vector<int> &vv, int k) {
        if (vv.size() == 0 || vv.back() < k)return -1;
        int l = 0, r = vv.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (vv[mid] >= k) r = mid;
            else l = mid + 1;
        }
        return vv[r];
    };
    map<int, vector<pair<int, int>>> del;
    Set se(n + 1);
    vector<PQ> vvv(n + 1);
    for (int i = 1; i <= n; i++) {
    
        for (auto j: pre[i]) {
            auto nex = lower(qq[j], i + 1);
            if (nex == -1)continue;
            int dis = nex - i + nex;
            nex = lower(qq[j], dis);
            if (nex == -1)continue;
            {
//                cerr << "emplace " << nex << " " << j << endl;
                vvv[nex].emplace(j);
                del[i].emplace_back(j, nex);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        vvv[i].emplace(-1);
        if (!vvv[i].empty())
            se.modify(1, 1, n, i, vvv[i].top());
    }

    vector<int> ans(q + 1);
    map<int, vector<pair<int, int >>> qu;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        qu[l].emplace_back(r, i);
    }
    for (int i = 1; i <= n; i++) {
        for (auto [r, id]: qu[i]) {
//            cerr << "q " << i << " " << r << endl;
            ans[id] = se.query(1, 1, n, i, r);
        }

        for (auto [j, pos]: del[i]) {
            vvv[pos].erase(j);
//            cerr << "erase " << pos << " " << j << endl;
            se.modify(1, 1, n, pos, vvv[pos].top());
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }

}