#include<iostream>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
using LL = long long;

#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
using namespace std;

struct Info {
    int mx = 0;
};

Info operator+(const Info &a, const Info &b){
    return {max(a.mx, b.mx)};
}

template<class Info>
struct SegmentTree{
    int n;
    vector<Info> info;

    SegmentTree() {}

    SegmentTree(int n, Info _init = Info()){
        init(vector<Info>(n, _init));
    }

    SegmentTree(const vector<Info> &_init){
        init(_init);
    }

    void init(const vector<Info> &_init){
        n = (int)_init.size();
        info.assign((n << 2) + 1, Info());
        function<void(int, int, int)> build = [&](int p, int l, int r){
            if (l == r){
                info[p] = _init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }

    void pull(int p){
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void modify(int p, int l, int r, int x, const Info &v){
        if (l == r){
            info[p] = info[p] + v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m){
            modify(2 * p, l, m, x, v);
        } 
        else{
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }

    void modify(int p, const Info &v){
        modify(1, 1, n, p, v);
    }

    Info query(int p, int l, int r, int x, int y){
        if (l > y || r < x){
            return Info();
        }
        if (l >= x && r <= y){
            return info[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
    }

    Info query(int l, int r){
        return query(1, 1, n, l, r);
    }
};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int N = 1e6;
    int n, m;
    cin >> n >> m;
    vector<vector<int> > pos(N + 1);
    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        for(int j = 1; j * j <= t; j++){
            if (t % j == 0){
                pos[j].push_back(i);
                if (j * j != t){
                    pos[t / j].push_back(i);
                }
            }
        }
    }
    vector<vector<pair<int, int> > > seg(n + 1);
    for(int i = 1; i <= N; i++){
        if (!pos[i].empty()){
            for(int j = 0, k = 0; j + 1 < pos[i].size(); j++){
                int a = pos[i][j], b = pos[i][j + 1];
                while(k < pos[i].size() and pos[i][k] - b < b - a) k++;
                if (k == pos[i].size()) break;
                seg[pos[i][k]].push_back({a, i});
            }
        }
    }
    vector<vector<pair<int, int> > > query(n + 1);
    vector<int> ans(m);
    for(int i = 0; i < m; i++){
        int l, r;
        cin >> l >> r;
        query[r].push_back({l, i});
    }
    SegmentTree<Info> st(n);
    for(int i = 1; i <= n; i++){
        for(auto [l, val] : seg[i]){
            st.modify(l, {val});
        }
        for(auto [l, id] : query[i]){
            ans[id] = st.query(l, i).mx;
        }
    }
    for(auto x : ans) cout << x << '\n';

}