#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int nxt[N+10],a[N+10];
vector<int>p[N+10];
int r[20][N+10];
int main(){
	int n,q;cin>>n>>q;
	for(int i=2;i<=N;i++){
		if(p[i].empty()){
			nxt[i]=n+1;
			for(int j=i;j<=N;j+=i){
				p[j].push_back(i);
			}
		}
	}
	r[0][n+1]=n+1;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>=1;i--){
		r[0][i]=r[0][i+1];
		for(auto& j:p[a[i]]){
			r[0][i]=min(r[0][i],nxt[j]);
			nxt[j]=i;
		}
	}
	for(int i=1;i<20;i++){
		for(int j=1;j<=n+1;j++){
			r[i][j]=r[i-1][r[i-1][j]];
		}
	}
	while(q--){
		int l,R,res=0;
		cin>>l>>R;
		for(int i=19;i>=0;i--){
			if(r[i][l]<=R){
				l=r[i][l];
				res+=1<<i;
			}
		}
		cout<<res+1<<'\n';
	}
}
