#include <iostream>
#include <vector>
#define PII pair<int, int>

using namespace std;

const int N = 1e6 + 5, B = 55;

int n, q, a[N], lst[N], vp[N], vs[N], vb[N], ids[N], idb[N], ans[N];
vector<int> d[N], now[N]; // pos
vector<PII> ins[N], qry[N];

void add(int p, int x)
{
    vp[p] = max(vp[p], x), vb[idb[p]] = max(vb[idb[p]], x), vs[ids[idb[p]]] = max(vs[ids[idb[p]]], x);
}

int sum(int p)
{
    int v = 0;
    for (int i = p; idb[i] == idb[p]; i++)
        v = max(v, vp[i]);
    for (int i = idb[p] + 1; ids[i] == ids[idb[p]]; i++)
        v = max(v, vb[i]);
    for (int i = ids[idb[p]] + 1; i <= ids[idb[n]]; i++)
        v = max(v, vs[i]);
    return v;
}

void init()
{
    for (int i = 1; i <= n; i++)
        idb[i] = (i - 1) / B + 1;
    for (int i = 1; i <= idb[n]; i++)
        ids[i] = (i - 1) / B + 1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1, l, r; i <= q; i++)
        cin >> l >> r, qry[r].push_back({l, i});
    for (int i = 1; i < N; i++)
        for (int j = i; j < N; j += i)
            d[j].push_back(i);
    for (int i = 1; i <= n; i++)
        for (auto x : d[a[i]])
        {
            if (lst[x])
                ins[2 * i - lst[x]].push_back({x, lst[x]});
            lst[x] = i;
        }
    init();
    for (int i = 1; i <= n; i++)
    {
        for (auto [v, p] : ins[i])
            now[v].push_back(p);
        for (auto x : d[a[i]])
            for (auto p : now[x])
                add(p, x);
        for (auto [l, j] : qry[i])
            ans[j] = sum(l);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
    return 0;
}