#include <bits/stdc++.h>
using namespace std;
struct AAA {
	int l, r, g;
} q[150005];
vector<AAA> seq;
int n, Q, c[150005], ans[150005], a[150005];
vector<int> num[1000005];
void add(int x, int y) {
	for (; x; x -= x & -x)
		c[x] = max(c[x], y);
}
int ask(int x) {
	int y = 0;
	for (; x <= n; x += x & -x)
		y = max(y, c[x]);
	return y;
}
int main() {
	scanf("%d%d", &n, &Q);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		num[a[i]].push_back(i);
	}
	for (int i = 1; i <= Q; ++i) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].g = i;
	}
	sort(q + 1, q + Q + 1, [](AAA p, AAA q) { return p.r < q.r; });
	for (int i = 1; i <= 1000000; ++i) {
		vector<int> v;
		for (int j = i; j <= 1000000; j += i)
			for (int k : num[j])
				v.push_back(k);
		sort(v.begin(), v.end());
		for (int j = 0; j + 1 < v.size(); ++j) {
			int x = v[j], y = v[j + 1];
			auto p = lower_bound(v.begin(), v.end(), y + y - x);
			if (p != v.end()) seq.push_back((AAA){x, *p, i});
		}
	}
	sort(seq.begin(), seq.end(), [](AAA p, AAA q) { return p.r < q.r; });
	int t = 0;
	for (int i = 1; i <= Q; ++i) {
		while (t <= seq.size() && seq[t].r <= q[i].r) {
			add(seq[t].l, seq[t].g);
			t++;
		}
		ans[q[i].g] = ask(q[i].l);
	}
	for (int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);
	return 0;
}