#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
#define fst first
#define scd second
#define SZ(s) ((int)s.size())
#define all(s) s.begin(),s.end()
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N=1.5e5+5; 
const int B=770;
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> pii;
template<class T,class I> inline void chkmax(T &a,I b){a=max(a,(T)b);}
template<class T,class I> inline void chkmin(T &a,I b){a=min(a,(T)b);}
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;static char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...I> inline void read(T &x,I &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char stk[70];short top=0;
	if(x<0) pt('-');
	do{stk[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
	while(top) pt(stk[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
int n,q,a[N],mx,ans[N];
vector<int> fac[N],pos[N];
vector<pii> mdf[N],ask[N];
namespace Blocks{
	inline int id(int x){
		return (x+B-1)/B;
	}
	inline int left(int x){
		return (x-1)*B+1;
	} 
	inline int right(int x){
		return min(mx,x*B);
	}
	int mx[N],val[N];
	inline int query(int x){
		int ans=0;
		for(int i=1;i<id(x);++i) chkmax(ans,mx[i]);
		for(int i=left(id(x));i<=x;++i) chkmax(ans,val[i]);
		return ans;
	}
	inline void upd(int x,int w){
		chkmax(val[x],w);
		chkmax(mx[id(x)],w);
	}
}
signed main(){
	read(n,q);
	for(int i=1;i<=n;++i) read(a[i]),chkmax(mx,a[i]);
	for(int i=1;i<=mx;++i){
		for(int j=i;j<=mx;j+=i){
			fac[j].eb(i);
		}
	} 
	for(int i=1;i<=n;++i) for(int j:fac[a[i]]) pos[j].eb(i);
	for(int i=1;i<=mx;++i){
		int k=SZ(pos[i]);
		for(int j=SZ(pos[i])-1;j>=1;--j){
			while(k&&pos[i][j]-pos[i][j-1]<=pos[i][k-1]-pos[i][j]) k--;
			auto check=[&](int x){
				return 0<=x&&x<SZ(pos[i])&&pos[i][j]-pos[i][j-1]<=pos[i][x]-pos[i][j];		
			};
			if(check(k)) mdf[pos[i][j-1]].eb(pos[i][k],i); 
		}
	}
	for(int l,r,i=1;i<=q;++i){
		read(l,r);
		ask[l].eb(r,i);
	}
	for(int l=mx;l;--l){
		for(pii qwq:mdf[l]){
			int r=qwq.fst,w=qwq.scd;
			Blocks::upd(r,w);
		}
		for(pii qwq:ask[l]){
			int r=qwq.fst,id=qwq.scd;
			ans[id]=Blocks::query(r);
		}
	}
	for(int i=1;i<=q;++i) println(ans[i]);
	return 0;
}