#include <bits/stdc++.h>
using namespace std;
int n,q,a[100005],np[100005],cnt[100005],nx[19][100005],p1,p2;
vector<int> p,fac[100005];
bool check(int ind) {
    for (int i=0; i<fac[ind].size(); i++) {
        if (cnt[fac[ind][i]]) return 0;
    }
    for (int i=0; i<fac[ind].size(); i++) cnt[fac[ind][i]]++;
    return 1;
}
void rem(int ind) {
    for (int i=0; i<fac[ind].size(); i++) {
        cnt[fac[ind][i]]--;
    }
}
void fun() {
    int l=0,r=0;
    while (l<n) {
        while (r<n and check(r)) r++;
        nx[0][l]=r;
        rem(l); l++;
    }
    nx[0][n]=n;
    for (int i=1; i<19; i++) {
        for (int j=0; j<=n; j++) {
            nx[i][j]=nx[i-1][nx[i-1][j]];
        }
    }
}
int getans(int l,int r) {
    int ind=18,ret=0,cur=l;
    while (ind>=0) {
        if (nx[ind][cur]<=r) {
            ret+=(1<<ind); cur=nx[ind][cur];
        }
        ind--;
    }
    return ret+1;
}
int main() {
    for (int i=2; i<=1e5; i++) {
        if (np[i]) continue;
        p.push_back(i);
        for (int j=2*i; j<=1e5; j+=i) {
            np[j]=1;
        }
    }
    cin>>n>>q;
    for (int i=0; i<n; i++) cin>>a[i];
    for (int i=0; i<n; i++) {
        int ind=0,x=a[i];
        while (p[ind]<318) {
            bool s=0;
            while (x%p[ind]==0) {
                x/=p[ind]; s=1;
            }
            if (s) fac[i].push_back(p[ind]);
            ind++;
        }
        if (x!=1) {
            fac[i].push_back(x);
        }
    }
    fun();
    for (int i=0; i<q; i++) {
        cin>>p1>>p2; p1--; p2--;
        cout<<getans(p1,p2)<<'\n';
    }
}