#include <bits/stdc++.h>

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;
}

std::tuple<int, int, int> aux[300 * 150000];
std::tuple<int, int, int> to_left[300 * 150000];

int main() {
    int n, q;

    n = getnr();
    q = getnr();

    std::vector<int> cnt(1 + MAX_E, 0);
    for (int d = 1; d <= MAX_E; d++) {
        for (int i = d; i <= MAX_E; i += d)
            cnt[i]++;
    }
    std::vector<std::vector<int>> divs(1 + MAX_E);
    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);

    std::vector<int> input(1 + n);
    std::vector<std::vector<int>> pos(1 + MAX_E);

    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++) {
        input[i] = getnr();
        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));

    std::vector<std::vector<std::pair<int, int>>> to_left(1 + n);
    std::vector<std::vector<std::pair<int, int>>> queries(1 + n);

    std::vector<std::unordered_set<int>> in_set(1 + n);

    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];
            while (last_p < pos[d].size() && pos[d][i] - pos[d][i - 1] > pos[d][last_p] - pos[d][i])
                last_p++;

            if (last_p < pos[d].size()) {
                int last = pos[d][last_p];
                if (in_set[first].find(last) == in_set[first].end()) {
                //if (in_set.find({first, last}) == in_set.end()) {
                    //aux[top_aux++] = {first, last, d};
                    to_left[last].push_back({d, first});
                    in_set[first].insert(last);
                    //std::cerr << first << "-" << last << " -> " << d << "\n";
                }
            }
        }
    }

    //int sum = 0;
    //for (auto it: in_set)
    //    sum += it.size();
    //std::cerr << "set elements: " << sum << "\n";

    std::mt19937 rng(1);

    std::vector<int> res(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        l = getnr();
        r = getnr();

        queries[r].push_back({i, l});
    }

    Fenwick T(n);

    int last_update = 0;
    for (int i = 1; i <= n; i++) {
        //while (last_update < top_aux && std::get<2>(to_left[last_update]) == i) {
        //    T.update(n + 1 - std::get<1>(to_left[last_update]), std::get<0>(to_left[last_update]));
        //    last_update++;
        //}
        //
        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 = 0; i < q; i++)
        std::cout << res[i] << "\n";

    return 0;
}