#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
#define For(i,x,y,...) for(int i=x,##__VA_ARGS__;i<=(y);++i)
#define rFor(i,x,y,...) for(int i=x,##__VA_ARGS__;i>=(y);--i)
#define Rep(i,x,y,...) for(int i=x,##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
#define mkp make_pair
#define mem(a,x,n) memset(a,x,sizeof(a[0])*(n+2))
typedef long long LL; typedef vector<int> Vi; typedef pair<int,int> Pii;
auto ckmax=[](auto &x,auto y) { return x<y ? x=y,true : false; };
auto ckmin=[](auto &x,auto y) { return y<x ? x=y,true : false; };
sfmt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) { return uniform_int_distribution<>(l,r)(mt); }
template<typename T=int>T read() { T x; cin>>x; return x; }

const int mod = 998244353;
struct mint {
	int x; mint(int x=0):x(x<0?x+mod:x<mod?x:x-mod){}
	mint(LL y) { y%=mod, x=y<0?y+mod:y; }
	mint& operator += (const mint &y) { x=x+y.x<mod?x+y.x:x+y.x-mod; return *this; }
	mint& operator -= (const mint &y) { x=x<y.x?x-y.x+mod:x-y.x; return *this; }
	mint& operator *= (const mint &y) { x=1ll*x*y.x%mod; return *this; }
	friend mint operator + (mint x,const mint &y) { return x+=y; }
	friend mint operator - (mint x,const mint &y) { return x-=y; }
	friend mint operator * (mint x,const mint &y) { return x*=y; }
};	mint Pow(mint x,LL y=mod-2) { mint z(1);for(;y;y>>=1,x*=x)if(y&1)z*=x;return z; }

const int N = 1e6+5;
int n,m,ans[N];
Vi pos[N];
vector<Pii> a[N],q[N];

#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
#define root int u=1,int l=1,int r=n
#define lson ls,l,mid
#define rson rs,mid+1,r
int t[N*4];
void mdf(int ql,int qr,int x,root) {
	if( qr < l || r < ql || x <= t[u] ) return;
	if( ql <= l && r <= qr ) { t[u] = x; return; }
	mdf(ql,qr,x,lson), mdf(ql,qr,x,rson);
}
int qry(int p,root) {
	if( l == r ) return t[u];
	return max(t[u], p<=mid?qry(p,lson):qry(p,rson));
}

void MAIN() {
	cin>>n>>m;
	For(i,1,n, x) {
		cin>>x;
		for(int j = 2; j*j <= x; ++j) if( !(x % j) ) {
			pos[j].pb(i);
			if( j*j != x ) pos[x/j].pb(i);
		}
		pos[x].pb(i);
	}
	rFor(i,1e6,2)
		Rep(j,1,sz(pos[i])) {
			auto it = lower_bound(all(pos[i]),pos[i][j]+pos[i][j]-pos[i][j-1]);
			if( it != pos[i].end() ) a[pos[i][j-1]].pb(*it,i);
		}
	For(i,1,m, l,r) if(cin>>l>>r; r-l > 1 ) q[l].pb(i,r);
	mdf(1,n,1);
	rFor(i,n,1) {
		for(auto [j,x] : a[i]) mdf(j,n,x);
		for(auto [id,j] : q[i]) ans[id] = qry(j);
	}
	For(i,1,m) cout<<ans[i]<<'\n';
} signed main() {
#ifdef FS
	freopen("in","r",stdin); freopen("out","w",stdout);
#endif
	ios::sync_with_stdio(0);cin.tie(0);
	int lft=1; while( lft-- ) {
		MAIN();
	}
	return 0;
}