#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;

long long u[100001],del[100001],l[100001],r[100001],p[21][100001];
vector<long long> d[100001];
vector<long long> st(21);
void resh(long long n)
{
    long long i,j;
    for(i=2;i<=n;i++)
    {
        if(u[i]==0)
        {
            del[i]=i;
            for(j=i*i;j<=n;j+=i)
            {
                u[j]=1;
                del[j]=i;
            }
        }
    }
}

long long fun(long long x,long long y,long long n)
{
    long long i,z,x1=x;
    for(i=0;i<=20;i++)
    {
        z=y&st[i];
        if(z!=0)
        {
            x1=p[i][x1];
        }
        if(x1==n)
        {
            return n;
        }
    }
    return x1;
}
int main()
{
      ios::sync_with_stdio(false);
      cin.tie(0);
      //freopen("input.txt","r",stdin);
      //freopen("output.txt","w",stdout);

       long long i,j,t,w,k,m,x,y,z,sum,mini,n,q,maxi,g,nov,rav,www,f,l1,r1,h;

        st[0]=1;
        for(i=1;i<=20;i++)
        {
            st[i]=st[i-1]*2;
        }
        resh(100000);
        cin>>n;
        cin>>t;
        vector<long long> a(n);
        for(i=0;i<n;i++)
        {
            cin>>a[i];
        }

        for(i=0;i<n;i++)
        {
            x=a[i];
            l[i]=-1;
            r[i]=n;
            while(x!=1)
            {
                y=del[x];
                d[y].push_back(i);
                while(x%y==0)
                {
                    x=x/y;
                }
            }
        }

        for(i=2;i<=100000;i++)
        {
            z=d[i].size();
            for(j=0;j<z-1;j++)
            {
                x=d[i][j];
                y=d[i][j+1];
                r[x]=min(r[x],y);
                l[y]=max(l[y],x);
            }
        }

        for(i=0;i<n;i++)
        {
            //cout<<"l["<<i<<"]="<<l[i]<<" r["<<i<<"]="<<r[i]<<endl;
        }
        p[0][n-1]=n;
        for(i=n-2;i>=0;i--)
        {
            p[0][i]=min(r[i],p[0][i+1]);
        }
        //cout<<"n="<<n<<endl;
        for(j=1;j<=20;j++)
        {
            for(i=0;i<n;i++)
            {
                x=p[j-1][i];
                if(x==n)
                {
                    p[j][i]=n;
                }
                else
                {
                    p[j][i]=p[j-1][x];
                }
                //cout<<"p["<<j<<"]["<<i<<"]="<<p[j][i]<<endl;
            }
        }

        //cout<<"aaaaaaaaaaaaaa"<<endl;
        for(q=0;q<t;q++)
        {
            cin>>x;
            cin>>y;
            x--;
            y--;
            l1=0;
            r1=n;
            while(l1!=r1-1)
            {

                w=(l1+r1)/2;
                //cout<<"l1="<<l1<<" r1="<<r1<<" w="<<w<<endl;
                h=fun(x,w,n);
                //cout<<"h="<<h<<endl;
                if(h>y)
                {
                    r1=w;
                }
                else
                {
                    l1=w;
                }
            }
            cout<<r1<<"\n";
        }

     return 0;
}





