#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vii         vector<pair<ll int, ll int>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
#define M  1000000007
#define MAXN   100005
ll int spf[100007];
mii m;
void sieve()
{
    spf[1]=1;
    spf[2]=2;
    rep(i,0,100005)
    spf[i]=i;
    for(int i=2;i*i<MAXN;i++)
    {
        if(spf[i]==i)
        {

            for(int j=i*i;j<MAXN;j+=i)
            {
                if(spf[j]==j)
                    spf[j]=i;
            }
        }
    }

}
ll int fun(ll int index,vector<ll int>&a)
{
    ll int val=a[index];
    ll int ans=a.size();
    while(val!=1)
    {
        ll int num=spf[val];
        if(m[num])
            ans=min(ans,m[num]);
        m[num]=index;
        while(val!=1 && spf[val]==num)
            val/=num;

    }
    return ans;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(15);
ll int t;
t=1;
sieve();
rep(w,0,t)
{
ll int n,q,l,r;
cin>>n>>q;
vi a(n);
rep(i,0,n)
cin>>a[i];
vi go(n);
for(int i=n-1;i>=0;i--)
{
 go[i]=fun(i,a);
 if(i+1<n)
    go[i]=min(go[i],go[i+1]);
}
ll int sz=(ceil(log2((double)n)));
ll int dp[n][sz];
rep(i,0,n)
dp[i][0]=go[i];
rep(i,1,sz)
{
    rep(j,0,n)
    {   if(dp[j][i-1]==n)
    dp[j][i]=n;
    else
        dp[j][i]=dp[dp[j][i-1]][i-1];

    }
}

rep(i,0,q)
{
    cin>>l>>r;
    l--;
    r--;
    ll int ans=0;
    for(int j=sz-1;j>=0;j--)
    {
        if(dp[l][j]<=r)
        {
            ans+=(1LL<<j);
            l=dp[l][j];
        }

    }
    ans++;

    cout<<ans<<"\n";
}
}


return 0;
}
