#include <bits/stdc++.h>
using namespace std;

int MOD=1000000007; //998244353
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}

int c[100000+1]={0};
int check(int x,int st)
{int flag=1;
    int y=x;
    for(int i=2;i*i<=x;++i)
    {
        if((y%i)==0)
        {if(c[i])
        {flag=0;
            break;}
            while((y%i)==0)
            {
                y=y/i;
            }

        }
    }
    if(y!=1)
         {
             if(c[y])
             {
                 flag=0;

             }
         }
    if(flag==0)
    {int d=st;
        for(int i=2;i*i<=st;++i)
        {if((d%i)==0)
            { c[i]=0;
                while((d%i)==0)
                    d=d/i;

            }
        }
        if(d!=1)
            c[d]=0;
        return 0;
    }
     y=x;
    for(int i=2;i*i<=x;++i)
    {
        if((y%i)==0)
        {c[i]=1;
            while((y%i)==0)
            {
                y=y/i;
            }

        }
    }
    if(y!=1)
         c[y]=1;
         return 1;
}

int main()
{
int n,q;
cin >> n>> q;
int a[n+1],r[n+2];
for(int i=1;i<=n;++i)
    scanf("%d" , a+i);

int st=1,fn=1;
 while(st<=n)
 {
     while((fn<n+1)&&(check(a[fn],a[st])==1))
     {
         fn++;
     }
     r[st]=fn;
     st++;


 }
int dp[20][n+1];
 for(int i=1;i<=n;++i)
    dp[0][i]=r[i];
 for(int i=1;i<20;++i)
 {
     for(int j=1;j<=n;++j)
     {
         if(dp[i-1][j]==n+1)
            dp[i][j]=n+1;
         else
            dp[i][j]=dp[i-1][dp[i-1][j]];
     }
 }

 for(int i=1;i<=q;++i)
 {
     int l,r;
     scanf("%d %d", &l,&r);
     int ans1=0;
     int curl=l;
     for(int i=19;i>-1;--i)
     {
         if(dp[i][l]<=r)
         {
             ans1+=(1<<i);
             l=dp[i][l];
         }
     }
     printf("%d\n" , ans1+1);
 }


}



