#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150005;
const int MAXV = 1000005;
vector<int> divisors[MAXV];
vector<pair<int, int>> intervals[MAXN];
vector<int> inds[MAXV];

struct Tree {
    typedef int T;
    static constexpr T unit = 0;
    T f(T a, T b) { return max(a, b); } // (any associative fn)
    vector<T> s; int n;
    Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
    void update(int pos, T val) {
        pos += n;
        for (s[pos] = f(s[pos], val); pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    for (int i = 1; i < MAXV; i++) {
        for (int j = i; j < MAXV; j += i) {
            divisors[j].push_back(i);
        }
    }

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int divisor : divisors[a[i]]) {
            inds[divisor].push_back(i);
        }
    }

    for (int i = 1; i < MAXV; i++) {
        int d_prev = -1;
        for (auto it = inds[i].begin(); it != inds[i].end(); it++) {
            if (d_prev != -1) {
                auto next_ind = lower_bound(it, inds[i].end(), *it + (*it - d_prev));
                if (next_ind != inds[i].end()) {
                    intervals[*next_ind].emplace_back(d_prev, i);
                }
            }
            d_prev = *it;
        }
    }

    vector<tuple<int, int, int>> queries(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        queries[i] = {r - 1, l - 1, i};
    }
    sort(queries.begin(), queries.end());

    Tree st(n);
    vector<int> res(n);
    int p = 0;
    for (int i = 0; i < n; i++) {
        for (auto [l, div] : intervals[i]) {
            st.update(l, div);
        }
        while (p < n && get<0>(queries[p]) == i) {
            res[get<2>(queries[p])] = st.query(get<1>(queries[p]), i + 1);
            p++;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << res[i] << "\n";
    }
}