// Created by CAD
#include <bits/stdc++.h>

#define fi first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x7fffffffffffffff
#define lson (p<<1)
#define rson (p<<1|1)
#define lowbit(i) (i&-i)
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define mst(name, value) memset(name,value,sizeof(name))
#define FOPEN freopen("C:\\Users\\14016\\Desktop\\cad.txt","r",stdin)
#define tst(x) cout<<#x<<"="<<x<<" "
#define test(x) cout<<#x<<"="<<x<<endl
#define ll long long

using namespace std;

const int maxn=1e5+5;
int a[maxn],lst[maxn],pos[maxn],fail[maxn][20];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        int x=a[i];
        for(int j=2;j*j<=x;++j){
            if(x%j==0){
                lst[i]=max(lst[i],pos[j]);
                pos[j]=i;
                while(x%j==0)
                    x/=j;
            }
        }
        if(x!=1){
            lst[i]=max(lst[i],pos[x]);
            pos[x]=i;
        }
        fail[i][0]=max(lst[i],fail[i-1][0]);
        for(int k=1;k<=19;++k)
            fail[i][k]=fail[fail[i][k-1]][k-1];
    }
    while(q--){
        int l,r;cin>>l>>r;
        int ans=0;
        for(int k=19;r>=l&&k>=0;--k){
            if(fail[r][k]>=l)
                ans+=(1<<k),r=fail[r][k];
        }
        cout<<ans+1<<endl;
    }
    return 0;
}
