#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q;
vector<int> p[N];
int a[N],nxt[N],dp[20][N];
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=2;i<=100000;i++){
        if(p[i].empty()){
            nxt[i]=n+1;//对于倍数进行处理
            for(int j=i;j<=100000;j+=i) p[j].push_back(i);//是j的因数
        }
    }
    dp[0][n+1]=n+1;
    for(int i=n;i>=1;i--){
        dp[0][i]=dp[0][i+1];
        for(int j:p[a[i]]){
            //cout<<j<<" ";
            dp[0][i]=min(dp[0][i],nxt[j]);//拓展子范围
            nxt[j]=i;//含有j因数的在i
        }
    }
    for(int i=1;i<20;i++)
        for(int j=1;j<=n+1;j++)
            dp[i][j]=dp[i-1][dp[i-1][j]];
    while(q--){
        int l,r,ans=0;
        scanf("%d%d",&l,&r);
        for(int i=19;i>=0;i--){
            if(dp[i][l]<=r){
                ans+=(1<<i);//二进制跳跃
                l=dp[i][l];
            }
        }
        cout<<ans+1<<endl;
    }
    //system("pause");
    return 0;
}