#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1000100;
const int maxm = 1000100;
const int N = 1000000;

int n, m, a[maxn], b[maxn], ans[maxn];
vector<int> di[maxm], vc[maxm];
vector<pii> md[maxn], qq[maxn];

namespace DS {
	int bel[maxn], blo, L[maxn], R[maxn], a[maxn], b[maxn];
	
	inline void init() {
		blo = sqrt(n);
		for (int i = 1; i <= n; ++i) {
			bel[i] = (i - 1) / blo + 1;
			if (!L[bel[i]]) {
				L[bel[i]] = i;
			}
			R[bel[i]] = i;
		}
	}
	
	inline void update(int x, int y) {
		a[x] = max(a[x], y);
		b[bel[x]] = max(b[bel[x]], y);
	}
	
	inline int query(int x) {
		int ans = 0;
		for (int i = x; i <= R[bel[x]]; ++i) {
			ans = max(ans, a[i]);
		}
		for (int i = bel[x] + 1; i <= bel[n]; ++i) {
			ans = max(ans, b[i]);
		}
		return ans;
	}
}

void solve() {
	for (int i = 1; i <= N; ++i) {
		for (int j = i; j <= N; j += i) {
			di[j].pb(i);
		}
	}
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		for (int x : di[a[i]]) {
			vc[x].pb(i);
		}
	}
	for (int i = 1, l, r; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		if (r - l <= 1) {
			continue;
		}
		qq[r].pb(l, i);
	}
	DS::init();
	for (int i = 1; i <= N; ++i) {
		int tot = 0;
		for (int x : vc[i]) {
			b[++tot] = x;
		}
		if (tot <= 2) {
			continue;
		}
		for (int j = 1, k = 1; j < tot; ++j) {
			while (k <= tot && b[k] < b[j + 1] * 2 - b[j]) {
				++k;
			}
			if (k > tot) {
				break;
			}
			md[b[k]].pb(b[j], i);
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (pii p : md[i]) {
			DS::update(p.fst, p.scd);
		}
		for (pii p : qq[i]) {
			ans[p.scd] = DS::query(p.fst);
		}
	}
	for (int i = 1; i <= m; ++i) {
		printf("%d\n", ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}