#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops, avx2")
const int MAX_E = 1000000;
struct Fenwick {
    std::vector<int> T;

    Fenwick(int n): T(1 + n) {}

    static inline int lsb(int x) { return x & (-x); }

    void update(int pos, int val) {
        while (pos < T.size() && val > T[pos]) {
            T[pos] = val;
            pos += lsb(pos);
        }
    }

    int query(int pos) {
        int res = 0;
        while (pos > 0) {
            res = std::max(res, T[pos]);
            pos -= lsb(pos);
        }
        return res;
    }
};

// const int BUFF = 1 << 14;
// char buff[BUFF];
// int curs = BUFF - 1;

// char getchr() {
//     curs++;
//     if (curs == BUFF) {
//         fread(buff, 1, BUFF, stdin);
//         curs = 0;
//     }
//     return buff[curs];
//  }

// int getnr() {
//     int nr = 0;
//     char chr = getchr();
//     while (!isdigit(chr)) chr = getchr();
    
//     while (isdigit(chr)) {
//         nr = nr * 10 + chr - '0';
//         chr = getchr();
//     }

//     return nr;
// }

int cnt[1 + MAX_E] = {0};
vector<int> divs[1 + MAX_E], pos[1 + MAX_E];
int input[150001] = {0};
vector<std::pair<int, int>> to_left[150001];
vector<std::pair<int, int>> queries[150001];
unordered_set<int> in_set[150001];

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
    int n, q;

    cin >> n >> q;

    for (int d = 1; d <= MAX_E; d++) {
        for (int i = d; i <= MAX_E; i += d)
            cnt[i]++;
    }

    for (int i = 0; i <= MAX_E; i++)
        divs[i].reserve(cnt[i]);

    for (int d = 1; d <= MAX_E; d++)
        for (int i = d; i <= MAX_E; i += d)
            divs[i].push_back(d);

    for (int i = 0; i <= MAX_E; i++)
        cnt[i] = 0;

    std::pair<int, int> largest = {0, 0};


    for (int i = 1; i <= n; i++) {
        cin >> input[i];
        for (auto it: divs[input[i]])
            cnt[it]++;
    }

    for (int i = 1; i <= MAX_E; i++)
        pos[i].reserve(cnt[i]);

    for (int i = 1; i <= n; i++) {
        for (auto it: divs[input[i]])
            pos[it].push_back(i);
    }

    for (int i = 1; i <= MAX_E; i++)
        largest = std::max(largest, std::make_pair((int)divs[i].size(), i));

    int top_aux = 0;
    for (int d = MAX_E; d >= 1; d--) {
        int last_p = 1;
        for (int i = 1; i < pos[d].size(); i++) {
            int first = pos[d][i - 1];
            int l = i, r = pos[d].size();
            while (r - l > 1) {
                int mid = (l + r) / 2;
                if (pos[d][i] - pos[d][i - 1] <= pos[d][mid] - pos[d][i])
                    r = mid;
                else
                    l = mid;
            }
            last_p = r;
            if (last_p < pos[d].size()) {
                int last = pos[d][last_p];
                if (!in_set[first].count(last)) {
                    to_left[last].push_back({d, first});
                    in_set[first].insert(last);
                }
            }
        }
    }
    std::vector<int> res(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        queries[r].push_back({i, l});
    }

    Fenwick T(n);

    int last_update = 0;
    for (int i = 1; i <= n; i++) {
        for (auto it: to_left[i]) {
            T.update(n + 1 - it.second, it.first);
        }
        for (auto it: queries[i]) {
            int id = it.first;
            int pos = it.second;

            res[id] = T.query(n + 1 - pos);
        }
    }

    for (int i : res)
        std::cout << i << "\n";

    return 0;
}