#include <bits/stdc++.h>
using namespace std;
int factorsOf[100001]={0};

void seive()
{
	for(int i=2;i<=100000;i++)
	{
		if(factorsOf[i]!=0)
			continue;
		for(int j=i;j<=100000;j+=i)
		{
			factorsOf[j]=i;
		}
	}
}
vector<int> primeFact(int n)
{
	vector<int> ans;
	while(n!=1)
	{
		int temp=factorsOf[n];
			ans.push_back(temp);
		while(n%temp==0)
			n=(n/temp);
	}
		
	return ans;
}
int main() {
	seive();
	int n,q;
	cin>>n>>q;
	int a[n+1];
	for(int i=0;i<n;i++)
		cin>>a[i];
	int nextSeen[n+1];
	for(int i=0;i<n;i++)
		nextSeen[i]=n;
	int next[100001];
	for(int i=0;i<=100000;i++)
		next[i]=n;
	int temp=n;

	for(int i=n-1;i>=0;i--)
	{
		vector<int> factors=primeFact(a[i]);
		 for(int f=0;f<factors.size();f++)
		 {
			//cout<<factors[f]<<" ";
			temp=min(temp,next[factors[f]]);
		 }
	//	 cout<<"\n";
		 nextSeen[i]=temp;
		 for(int f=0;f<factors.size();f++)
		 	next[factors[f]]=i;
	}
	
	int dp[20][n+1];
	for(int i=0;i<n;i++)
		dp[0][i]=nextSeen[i];
	for(int i=1;i<20;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(dp[i-1][j]!=n)
			{
				dp[i][j]=dp[i-1][dp[i-1][j]];
			}
			else
				dp[i][j]=n;
		}
	}
	for(int i=0;i<q;i++)
	{
		int l,r,count=0;
		cin>>l>>r;
		l--,r--;
		int maxLifts=19;
		while(nextSeen[l]<=r)
		{
			while(dp[maxLifts][l]>r) maxLifts--;
			count+=(1<<maxLifts);
			l=dp[maxLifts][l];
		}
		cout<<count+1<<"\n";
	 }
	
	// your code goes here
	return 0;
}