#include <bits/stdc++.h>

constexpr int MAXS1 = 2.65e7 * 1.5;
constexpr int MAXS2 = 2.5e7 * 1.5;
constexpr int MAXN = 1.5e5 + 19;
constexpr int MAXA = 1e6 + 19;

struct Edge {
    int to, next;
} edge[MAXS1];
int edge_tot;
void insert(int &h, int x) {
    ++edge_tot;
    edge[edge_tot].to = x;
    edge[edge_tot].next = h;
    h = edge_tot;
}
int divs[MAXA], pos[MAXA];

struct Page {
    int r, v, next;
} page[MAXS2];
int page_tot;
int interv[MAXN];
void insert(int &h, int r, int v) {
    ++page_tot;
    page[page_tot].r = r;
    page[page_tot].v = v;
    page[page_tot].next = h;
    h = page_tot;
}

int n, q;
int a[MAXN];

struct BIT {
    int tr[MAXN];
    void update(int x, int k) {
        for (; x <= n; x += x & -x) {
            tr[x] = std::max(tr[x], k);
        }
    }
    int query(int x) {
        int res = 0;
        for (; x; x -= x & -x) {
            res = std::max(res, tr[x]);
        }
        return res;
    }
} bit;

struct Query {
    int l, r, id;
} query[MAXN];
int ans[MAXN];

int main() {
    std::cin >> n >> q;

    int L = 0;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        L = std::max(L, a[i]);
    }

    for (int d = 1; d <= L; ++d) {
        for (int i = d; i <= L; i += d) {
            insert(divs[i], d);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = divs[a[i]]; j; j = edge[j].next) {
            int d = edge[j].to;
            insert(pos[d], i);
        }
    }

    for (int i = 1; i <= L; ++i) {
        // std::cout << "pos[" << i << "]: ";

        std::vector<int> p;
        for (int j = pos[i]; j; j = edge[j].next) {
            p.push_back(edge[j].to);
        }
        std::reverse(p.begin(), p.end());

        int last = p.size() - 1;
        for (int j = p.size() - 3; j >= 0; --j) {
            int x = p[j], y = p[j + 1];
            while (last - 1 > j + 1 && y - x <= p[last - 1] - y) {
                --last;
            }
            if (y - x <= p[last] - y) {
                insert(interv[x], p[last], i);
            }
        }
    }

    for (int i = 1; i <= q; ++i) {
        std::cin >> query[i].l >> query[i].r;
        query[i].id = i;
    }
    std::sort(query + 1, query + 1 + q, [](const auto &x, const auto &y) {
        return x.l > y.l;
    });

    int now = n + 1;
    for (int _ = 1; _ <= q; ++_) {
        auto [l, r, id] = query[_];
        while (now > l) {
            --now;
            for (int i = interv[now]; i; i = page[i].next) {
                int r = page[i].r, v = page[i].v;
                bit.update(r, v);
            }
        }
        ans[id] = bit.query(r);
    }
    for (int i = 1; i <= q; ++i) {
        std::cout << ans[i] << '\n';
    }
}