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

// Explanation: OleschY

// we will calculate for each number, what are its prime factors. Note: We are not interested about
// how often each factor appears. We are happy with knowing whether it appears as prime factor
vector<int> p[100005];

// The Input
int a[100005];

// This is our dp structure.
// First we will fill dp[0][i]. This is equivalent to go_l from the editorial
// dp[0][i] points to the first element of a[n] which has a common prime factor with a[i]
// In a second dp-step we will create dp[j>0][i]. d[0][i] denotes one step, d[1][i] denotes 2 steps,
// d[2][i] denotes 4 steps from i, and so on. dp[j][i] denotes 1<<j steps from i.
int dp[20][100005];

// in the first step of calculating dp[0][i] we will iterate from right to left over a[i]. while
// iterating we will save the next occurance of the prime actor f in nex[f]
int nex[100005];

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

    // This is a sieve. We fill p[i] with all the prime factors of i
    for (int i=2;i<=MX;i++)
    {
        // p[i] is empty, so i is a prime, so we will mark this as a factor in all numbers p[k*i] with k>=2
        if (p[i].empty())
        {
            // we initialise nex[i] for all i which are prime. It points to the first elkement after the end of a[n]
            nex[i]=n+1;
            for (int j=i;j<=MX;j+=i)
            p[j].push_back(i);
        }
    }
    // we initialise the first value. dp[0][n+1] is out of bounds but has to point to n+1
    // so we can always do multiple jumps and still end up in n+1
    dp[0][n+1]=n+1;

    // this is the first step of generating dp[0][i] which is equal to go_l
    for (int i=n;i>0;i--)
    {
        // the segment starting from dp[0][i] can go at most as far as dp[0][i+1]. Then we will have a
        // prime factor collision of a[i+1] and a[dp[0][i+1]]. Thats how we initialise dp[0][i]
        dp[0][i]=dp[0][i+1];
        // Now we need to check for each prime factor of a[i] where its next occurance is.
        for (int j:p[a[i]])
        {
            // to check this we can use our array nex[j].
            // The segment can't go further than the earliest reoccuring primefactor
            dp[0][i]=min(dp[0][i],nex[j]);
            // afterwards we have to update nex[j]. a[i] has the prime factor j.
            // so the next occurence of primefactor j will be a position i
            nex[j]=i;
        }
    }
    // now we can create the exponential jumps for dp[i>0][j].
    // For that we use that e.g. two jumps of length 4 equal one jump of length 8
    // this is manifested in dp[i][j]=dp[i-1][dp[i-1][j]];
    for (int i=1;i<20;i++)
    {
        for (int j=1;j<=n+1;j++)
        dp[i][j]=dp[i-1][dp[i-1][j]];
    }
    // now solving the queries
    while (q--)
    {
        int l,r,ans=0;
        scanf("%d%d",&l,&r);
        // we try jumps starting with the longest jump 1<<19==524288
        // (since MX=100000, i=17 shouldve been enough? its no big performance difference though)
        for (int i=19;i>=0;i--)
        {
            // If we can make a jump and don't overstep r then we make the jump. Else we reduce the jumpsize
            // Note: Each jump only must be checked once. the  "if (dp[i][l]<=r)" is enough
            // we don't need "while(dp[i][l]<=r)" since the jumps are in the form 2**i and we start testing with jumplength>MX/2
            if (dp[i][l]<=r)
            {
                ans+=(1<<i);
                l=dp[i][l];
            }
        }
        // Answer. hooray!
        printf("%d\n",ans+1);
    }
}