#include "bits/stdc++.h"

using namespace std;

void solve() {
    //求 1e6所以的因子
    int lim = 1000000;
    vector<vector<int>> f(lim + 1);

    for (int i = 1; i <= lim; i++) {
        for (int j = i; j <= lim; j += i) {
            f[j].push_back(i);
        }
    }
    vector<vector<int>> pos(lim + 1);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (auto &j: f[a[i]]) {
            pos[j].push_back(i);
        }
    }

    auto check = [&](int x, vector<int> &a) {
        if (a.empty()) return -1;
        if (a.back() < x) return -1;
        int l = 0, r = a.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return a[l];
    };

    // 记录更新节点
    vector<vector<pair<int, int>>> add(n + 1);
    for (int i = 1; i <= n; i++) {
        //对于每个因子
        for (auto &j: f[a[i]]) {

            if (j == 1) continue;
            //找到下个位置
            int next = check(i + 1, pos[j]);
            if (next == -1) {
                continue;
            }
            int dis = next - i;
            next = check(next + dis, pos[j]);
            if (next == -1) {
                continue;
            }
            add[i].emplace_back(next, j);
        }
        reverse(add[i].begin(), add[i].end());
    }

    vector<int> fiw(n + 1, 1);
    auto update = [&](int x, int y) {
        for (int i = x; i <= n; i += i & -i) {
            if (fiw[i] >= y) break;
            fiw[i] = y;
//            fiw[i] = max(fiw[i], y);
        }
    };

    auto query = [&](int x) {
        int res = 0;
        for (int i = x; i; i -= i & -i) {
            res = max(res, fiw[i]);
        }
        return res;
    };




    vector<int> ans(q);
    vector<vector<pair<int, int>>> querys(n + 1);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        querys[l].emplace_back(r, i);
    }

    for (int i = n; i >= 1; i--) {
        for (auto [r, v]: add[i]) {
            update(r, v);
        }

        for (auto [r, id]: querys[i]) {
            ans[id] = query(r);
        }
    }

    for (auto i: ans) {
        cout << i << endl;
    }

}

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

}