#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};
struct Max {
    int x = 0;
};

Max operator+(const Max &a, const Max &b) {
    return {std::max(a.x, b.x)};
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    const int m = *std::max_element(a.begin(), a.end());
    
    std::vector<std::vector<int>> d(m + 1);
    for (int i = 1; i <= m; i++) {
        for (int j = i; j <= m; j += i) {
            d[j].push_back(i);
        }
    }
    
    std::vector<std::vector<int>> f(m + 1);
    for (int i = 0; i < n; i++) {
        for (auto x : d[a[i]]) {
            f[x].push_back(i);
        }
    }
    
    std::vector<std::array<int, 3>> e;
    for (int x = 1; x <= m; x++) {
        for (int i = 1; i + 1 < f[x].size(); i++) {
            auto it = std::lower_bound(f[x].begin(), f[x].end(), f[x][i] * 2 - f[x][i - 1]);
            if (it != f[x].end()) {
                e.push_back({f[x][i - 1], *it, x});
            }
        }
    }
    
    std::sort(e.begin(), e.end(), std::greater());
    
    std::vector<std::array<int, 3>> ask(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        l--;
        ask[i] = {l, r, i};
    }
    std::sort(ask.begin(), ask.end(), std::greater());
    
    Fenwick<Max> fen(n);
    
    std::vector<int> ans(q);
    for (int j = 0; auto [l, r, i] : ask) {
        while (j < e.size() && e[j][0] >= l) {
            fen.add(e[j][1], {e[j][2]});
            j++;
        }
        ans[i] = fen.sum(r).x;
    }
    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << "\n";
    }
    
    return 0;
}