#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int mod = 998244353;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int inf = 0x3f3f3f3f;
struct Q {
	int l, r;
	int id;
};

bool cmp(Q& a, Q& b)
{
	if (a.r != b.r) {
		return a.r < b.r;
	}
	return a.l < b.l;
}
int n, m, a[N];
vector<Q> q;

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		int l, r; cin >> l >> r;
		q.push_back({ l , r, i });
	}
	vector<int> fac[M];
	for (int i = 1; i <= 1e6; i++) {
		for (int j = i; j <= 1e6; j+= i) {
			fac[j].push_back(i);
		}
	}
	vector<int>  pos[N];
	for (int i = 1; i <= n; i++) {
		for (auto s : fac[a[i]]) {
			pos[s].push_back(i);
		}
	}
	sort(q.begin(), q.end(), cmp);
	vector<pair<int, int>> R[N];
	for (int i = 1; i <= 1e6; i++) {
		int nn = pos[i].size();
		for (int j = 0; j  + 2 < nn; i++) {
			int r = pos[i][j + 1] * 2 - pos[i][j];
			int idx = std::lower_bound(pos[i].begin(), pos[i].end(), r) - pos[i].begin();
			if (idx == nn) {
				continue;
			}
			R[pos[i][idx]].push_back({ pos[i][j], i });
		}
	}
	vector<int> id(n + 1), f(n + 1 , 0), mx(n + 1 , 0);
	int len = sqrt(n) + 1;
	for (int i = 1; i <= n; i++) {
		id[i] = i / len + 1;
	}
	auto insert = [&](int x, int v)-> void {
		mx[x] = max(mx[x], v);
		f[id[x]] = max(f [id[x]], mx[x]);
	};
	auto query = [&](int l, int r) -> int {
		int idl = id[l], idr = id[r];
		int res = 0;
		if (idl == idr) {
			for (int i = l; i <= r; i++) {
				res = std::max(res, mx[i]);
			}
			return res;
		}
		for (int i = l; id[i] == idl; i++) {
			res = std::max(res, mx[i]);
		}
		for (int i = r; id[i] == idr; i--) {
			res = std::max(res, mx[i]);
		}
		for (int i = idl + 1; i < idr; i++) {
			res = std::max(res, f[i]);
		}
		return res;
		};
	vector<int> ans(m + 1, 0);
	for (int i = 0, j = 0; i < m; i++) {
		auto [l, r, id] = q[i];
		while (j < r) {
			j++;
			for (auto [cc, v] : R[j]) {
				insert(cc, v);
			}
		}
		ans[id] = query(l, r);
	}
	for (int i = 0; i < m; i++) {
		std::cout << ans[i] << "\n";
	}
}


signed main() {
	int T = 1;
	while (T--)
		solve();
	return 0;
}