#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int N = 1e6 + 5;

vector <pii> vec2[N], qry[N];
vector <int> g[N], vec[N];
int ans[N], f[N];
int n, q;

void add(int x, int y) {
	while (x) {
		f[x] = max(f[x], y);
		x &= (x - 1);
	}
}

int query(int x) {
	int ans = 1;
	while (x <= n) {
		ans = max(ans, f[x]);
		x += (x & -x);
	}
	return ans;
}

int main() {
	for (int i = 2; i <= N - 5; i++) {
		for (int j = i; j <= N - 5; j += i) g[j].push_back(i);
	}
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		int a;
		scanf("%d", &a);
		for (auto j : g[a]) vec[j].push_back(i);
	}
	for (int i = 2; i <= N - 5; i++) {
		int len = (int)vec[i].size();
		int now = len - 1;
		for (int j = len - 2; j >= 1; j--) {
			int minr = vec[i][j] * 2 - vec[i][j - 1];
			while (vec[i][now - 1] >= minr) --now;
			if (vec[i][now] >= minr) {
				vec2[vec[i][now]].emplace_back(vec[i][j - 1], i);
			}
		}
	}
	for (int i = 1; i <= q; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		qry[r].emplace_back(l, i);
	}
	for (int i = 1; i <= n; i++) {
		for (auto j : vec2[i]) add(j.first, j.second);
		for (auto j : qry[i]) ans[j.second] = query(j.first);
	}
	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;
}