#include <bits/stdc++.h>
#define lowbit(i) (i & (-i))
using namespace std;
const int mod = 998244353;
const int N = 5e3 + 10;
const int M = 1e6 + 10;
const int maxn = 2e5 + 5;
vector<int> d[M];
vector<int> tong[M];
class BIT
{
public:
    int b[maxn];
    int n;
    void add(int x, int val)
    {
        for (int i = x; i <= n; i += lowbit(i))
            b[i] = max(b[i], val);
    }
    int s(int x)
    {
        int ret = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            ret = max(ret, b[i]);
        return ret;
    }
} bit;
void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < M; i++)
    {
        for (int j = i; j < M; j += i)
        {
            d[j].push_back(i);
        }
    }
    bit.n = n;
    int mx = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for (auto j : d[a[i]])
        {
            tong[j].push_back(i);
        }
        mx = max(mx, a[i]);
    }
    vector<vector<pair<int, int>>> qry(n + 1, vector<pair<int, int>>());
    vector<vector<pair<int, int>>> val(n + 1, vector<pair<int, int>>());
    for (int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        qry[x].push_back(pair{y, i});
    }

    for (int i = 1; i <= mx; i++)
    {
        for (int j = 0; j < (int)tong[i].size() - 1; j++)
        {
            int d = tong[i][j + 1] - tong[i][j];
            int r = tong[i][j] + d + d;
            r = lower_bound(tong[i].begin() + j, tong[i].end(), r)-tong[i].begin();
            if(r<tong[i].size())
            val[tong[i][j]].push_back(pair{tong[i][r], i});
        }
    }
    vector<int> ans(q + 1, 1);
    for (int i = n; i >= 1; i--)
    {
        for (auto [pos, val] : val[i])
        {
            bit.add(pos, val);
        }
        for (auto [r, id] : qry[i])
        {
            ans[id] = bit.s(r);
        }
    }
    for(int i= 1;i<=q;i++)
    {
        cout<<ans[i]<<'\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
}