#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=1.5e5+10,M=1e6+10;
int n,m,a[N];
int cnt,pri[M],vis[M],mn[M];
void init(int n=M-1){
	for(int i=2;i<=n;i++){
		if(!vis[i])pri[++cnt]=i,mn[i]=i;
		for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
			vis[i*pri[j]]=1;
			mn[i*pri[j]]=pri[j];
			if(i%pri[j]==0)break;
		}
	}
}
vector<int>pos[M];
vector<pair<int,int>>o[N],q[N];
int c[N],ans[N];
void add(int x,int y){
	for(;x<=n;x+=x&-x)c[x]=max(c[x],y);
}
int get(int x,int y=0){
	for(;x;x^=x&-x)y=max(y,c[x]);
	return y;
}
int main(){
	scanf("%d%d",&n,&m),init();
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		int x=a[i];
		vector<int>t;
		for(;x>1;x/=mn[x])t.push_back(mn[x]);
		function<void(int,int)>dfs=[&](int l,int cur){
			if(l==t.size())return pos[cur].push_back(i);
			int r=l+1;
			for(;r<t.size()&&t[l]==t[r];r++);
			for(int i=l;i<=r;i++)dfs(r,cur),cur*=t[l];
		};
		dfs(0,1);
	}
	for(int i=1,l,r;i<=m;i++){
		scanf("%d%d",&l,&r);
		q[l].push_back({r,i});
	}
	for(int i=1;i<M;i++){
		if(pos[i].empty())continue;
		for(int j=1,x=0;j+1<pos[i].size();j++){
			for(;x<pos[i].size()&&pos[i][x]-pos[i][j]<pos[i][j]-pos[i][j-1];x++);
			if(x<pos[i].size())o[pos[i][j-1]].push_back({pos[i][x],i});
		}
	}
	for(int i=n;i>=1;i--){
		for(auto [x,w]:o[i])add(x,w);
		for(auto [x,id]:q[i])ans[id]=get(x);
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif