#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize(3, "Ofast", "inline")
#pragma GCC optimize("Ofast,unroll-loops")
#define pb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair <ll,ll> P;
#define _for(x,y,z) for (int x(y),_(z); x<=_; ++x)
#define _rep(x,y,z) for (int x(y),_(z); x>=_; --x)
inline int read(){
	int x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline void _init(){
	#ifdef LOCAL
		assert(freopen("test.in", "r", stdin));
		assert(freopen("test.out", "w", stdout));
	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
}
const int N = 1000000;
const int B = 320;
int n,q,a[100005],bl[100005],bv[100005],lft[100005],rht[100005],ans[1000005];
vector<int>v[1000005],fc[1000005];
vector<pair<int,int>>tg[1000005];

vector<pair<int,int>>qr[1000005];
inline void upd(int x, int v){
	if(v>a[x]) a[x]=v;
	if(v>bv[bl[x]]) bv[bl[x]]=v; 
}

inline int qry(int l,int r){
	int ans = 0;
	if(bl[l] == bl[r]){
		for(int i=l; i<=r; i++)
			if(a[i] > ans) ans = a[i];
		return ans;
	}
	for(int i=bl[l]+1; i<=bl[r]-1; i++){
		if(bv[i] > ans) ans = bv[i];
	}
	for(int i=l; bl[l]==bl[i] ; i++){
		if(a[i] > ans) ans = a[i];
	}
	for(int i=r; bl[r]==bl[i] ; i--){
		if(a[i] > ans) ans = a[i];
	}
	return ans;
}
void procedure() {
	n=read(), q=read();
	for(int i=1;i<=n;i++) a[i]=read(), bl[i]=(i-1)/B+1;
	for(int i=1;i<=n;i++){
		for(auto x: fc[a[i]]){
			v[x].pb(i);
		}
	}
	memset(a, 0, sizeof(a));
	for(ll i=1;i<=N;i++){
		ll sz = v[i].size();
		if(sz <= 2) continue;
		ll pt = sz-2;
		for(ll j=sz-1; j>=2; j--){
			while(pt >= 1 && (v[i][pt]-v[i][pt-1] > v[i][j]-v[i][pt] || pt >= j)) pt --;
			if(pt >= 1) tg[v[i][j]].pb(v[i][pt-1], i);
		}
	}

	for(int i=1;i<=q;i++){
		int l=read(), r=read();
		qr[r].pb(l, i);
	}
	for(int r=1;r<=n;r++){
		for(auto pr: tg[r]){
			upd(pr.fi, pr.se);
		}
		for(auto pr: qr[r]){
			ans[pr.se] = qry(pr.fi, r);
		}
	}
	for(int i=1;i<=q;i++) printf("%d\n", ans[i]);
}

void init() {
	for(int i=1;i<=N;i++){
		for(int j=i;j<=N;j+=i){
			fc[j].pb(i);
		}
	}
}

int main() {
	_init(), init();
	int T=1;
	while(T--) procedure();
	return 0;
}