#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;

struct SegmentTree {
private:
    ll n;
    vector<ll> node;
    ll ID = 0LL; // min -> INF, max, sum -> 0
    inline ll func(ll a, ll b){return max(a, b);} /////////

public:
    SegmentTree(vector<ll> v) {
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, ID);
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = func(node[2*i+1], node[2*i+2]);
    }

    void update(ll x, ll val) {
        x += (n - 1);
        node[x] = val;
        while(x > 0) {
            x = (x - 1) / 2;
            node[x] = func(node[2*x+1], node[2*x+2]);
        }
    }

    ll get(ll a, ll b, ll k=0, ll l=0, ll r=-1) {
        if(r < 0) r = n;
        if(r <= a || b <= l) return ID;
        if(a <= l && r <= b) return node[k];

        ll vl = get(a, b, 2*k+1, l, (l+r)/2);
        ll vr = get(a, b, 2*k+2, (l+r)/2, r);
        return func(vl, vr);
    }
};

vector<ll> divisor(ll n) {
    vector<ll> v1, v2;
    for(ll i = 1; i * i <= n; i ++) {
        if(n % i == 0) {
            if(i * i != n) v2.pb(n / i);
            v1.pb(i);
        }
    }
    reverse(all(v1));
    foa(e, v1) v2.pb(e);
    return v2;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    SegmentTree seg(vector(n, 0LL));
    vector<vector<pair<ll, ll>>> query(n);
    vector<ll> ans(q);
    rep(i, q) {
        ll x, y;
        cin >> x >> y;
        x --;
        query[x].push_back({y, i});
    }
    ll N = 1000000;
    vector<queue<ll>> v(N + 1);
    vector<ll> bb(N + 1, n);
    vector<ll> c(n, 0LL);
    for(ll i = n - 1; i >= 0; i --) {
        ll id = n + 1;
        foa(e, divisor(a[i])) {
            while(!v[e].empty() and v[e].front() >= id) v[e].pop();  
            if((int)v[e].size() < 2) {
                v[e].push(i);
                bb[e] = i;
                continue;
            }
            ll idx = n + 1;
            while(!v[e].empty() and v[e].front() - bb[e] >= bb[e] - i) {
                idx = v[e].front();
                v[e].pop();
            }
            id = idx;
            if(c[idx] < e) {
                c[idx] = e;
                seg.update(idx, e);
            }
            
            bb[e] = i;
            v[e].push(i);
        }
        for(auto [x, j] : query[i]) {
            ans[j] = seg.get(i, x);
        }
    }
    foa(e, ans) cout << e << endl;
    return 0;
}