#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef unsigned long long u64;
typedef double lf;

const int maxv = 1000500;
const int maxn = 150500;

vector<int> divs[maxv];
vector<int> occ[maxv];

vector<int> ans;

struct event {
    int type;
    int y;
    int val;
};

vector<event> events[maxn];

struct fenwick {
    int t[maxn];
    int n;
    fenwick()  {
    }

    void inc(int i, int val) {
        for (; i < n; i |= i + 1) {
            t[i] = max(t[i], val);
        }
    }
    int get(int i) {
        int res = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) {
            res = max(res, t[i]);
        }
        return res;
    }
};

// const int hsz = 1 << 18;
// const int tsz = 1 << 19;

// int t[tsz];

// void put(int v, int tl, int tr, int l, int r, int val) {
//     if (l >= r) {
//         return;
//     }
//     if (l == tl && r == tr) {
//         t[v] = max(t[v], val);
//         return;
//     }
//     int tm = (tl + tr) / 2;
//     put(v * 2, tl, tm, l, min(r, tm), val);
//     put(v * 2 + 1, tm, tr, max(l, tm), r, val);
// }

// int get(int v, int tl, int tr, int pos) {
//     if (tl + 1 == tr) {
//         return t[v];
//     }
//     int tm = (tl + tr) / 2;
//     if (pos < tm) {
//         return max(t[v], get(v * 2, tl, tm, pos));
//     } else {
//         return max(t[v], get(v * 2 + 1, tm, tr, pos));
//     }
// }

// int get_lower(int pos) {
//     pos += hsz;
//     int res = 0;
//     while (pos > 0) {
//         res = max(res, t[pos]);
//         pos /= 2;
//     }
//     return res;
// }

void solve() {
    auto t0 = clock();
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<char> used(maxv, false);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        used[a[i]] = 1;
    }
    
    
    for (int i = 1; i < maxv; i++) {
        for (int j = i; j < maxv; j += i) {
            if (used[j]) {
                divs[j].push_back(i);
            }
        }
    }
    auto t1 = clock();
    cerr << "divs " << (t1 - t0) * 1. / CLOCKS_PER_SEC << endl;
    vector<char> ds(maxv, 0);
    for (int i = 0; i < n; i++) {
        for (int d : divs[a[i]]) {
            if (d != 1) {
                ds[d] = 1;
                occ[d].push_back(i);
            }
        }
    }
    auto t2 = clock();
    cerr << "occ " << (t2 - t1) * 1. / CLOCKS_PER_SEC << endl;
    for (int d = maxv - 1; d >= 0; --d) {
        if (!ds[d]) {
            continue;
        }
        const auto& cur = occ[d];
        for (size_t i = 0; i + 1 < cur.size(); ++i) {
            int a = cur[i];
            int b = cur[i + 1];
            int c = 2 * b - a;
            if (c >= n) {
                continue;
            }
            int idx = min(cur.size(), i + 20);
            auto it = lower_bound(cur.begin() + i, cur.begin() + idx, c);
            if (it != cur.end()) {
                events[*it].push_back({
                    .type = 1,
                    .y = a,
                    .val = d,
                });
            }
        }
    }
    auto t3 = clock();
    cerr << "events " << (t3 - t2) * 1. / CLOCKS_PER_SEC << endl;

    ans.resize(q);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        if (r - l <= 1) {
            ans[i] = 0;
            continue;
        }
        ans[i] = 1;
        events[r].push_back({
            .type = 0,
            .y = l,
            .val = i,
        });
    }
    auto t4 = clock();
    cerr << "input " << (t4 - t3) * 1. / CLOCKS_PER_SEC << endl;

    // fill(t, t + tsz, 0);
    // sort(events.begin(), events.end());
    fenwick f;
    for (int i = 0; i < n; ++i) {
        for (const auto& e : events[i]) {
            if (e.type == 0) {
                ans[e.val] = f.get(e.y);
                // ans[e.val] = get_lower(e.y);
                // cerr << "get " << e.y << " " << ans[e.idx] << "\n";
            } else {
                f.inc(e.y, e.val);
                // put(1, 0, hsz, 0, e.y + 1, e.val);
                // cerr << "put " << e.y << " " << e.val << "\n";
                // for (int i = 0; i < n; ++i) {
                //     cerr << get(1, 0, hsz, i) << " ";
                // }
                // cerr << endl;
            }
        }
    }
    auto t5 = clock();
    cerr << "solve " << (t5 - t4) * 1. / CLOCKS_PER_SEC << endl;
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
}