#include "bits/stdc++.h"

using namespace std;

//8 8
//8 24 4 6 6 7 3 3
//1 5
//2 6
//3 7
//5 8
//4 8
//1 3
//2 5
//3 8
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;
            }
//            cerr <<  i << " " << next << " " << j << endl;
            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;
        }
    };

    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;
//        cerr << l << " " << r << endl;
        querys[l].emplace_back(r, i);
    }
    vector<int> last(lim + 1, lim);
    for (int i = n; i >= 1; i--) {
        for (auto [r, v]: add[i]) {
//            cerr<< "update " << i << " " << r << " " << v << endl;
            if (last[v] < r) continue;
            last[v] = r;
            update(r, v);
        }

        for (auto [r, id]: querys[i]) {
//            cerr << "query " << i << " " << r << " " << id << endl;
            ans[id] = query(r);
        }
    }

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

}

int main() {
    //记录时间
    auto start = clock();
//    ios::sync_with_stdio(false), cin.tie(0);
    freopen(R"(C:\Users\DELLPC\Desktop\code\T\input.txt)", "r", stdin);
    freopen(R"(C:\Users\DELLPC\Desktop\code\T\output.txt)", "w", stdout);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    auto end = clock();
    cerr << "Time: " << (double) (end - start) / CLOCKS_PER_SEC << "s" << endl;

}