#include <bits/stdc++.h>
#define ll long long

using namespace std;

vector<ll> primeFactors(ll num)
{
    vector<ll> ret;
    for(ll i = 2; i * i <= num; i++)
    {
        if(num % i == 0)
            ret.push_back(i);
        while(num % i == 0)
            num /= i;
    }
    if(num != 1)
        ret.push_back(num);
    return ret;
}

vector<ll> nextv;
vector<vector<ll>> nexth;
ll n, h;

ll advance(ll idx, ll steps)
{
    if(steps == 0)
        return idx;
    ll i = 0;
    while((1 << i) <= steps)
        i++;
    i--;
    ll nsteps = steps - (1ll << i);
    return advance(nexth[idx][i], nsteps);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q;
    cin >> n >> q;
    vector<ll> v(n + 1);
    for(ll i = 1; i <= n; i++)
        cin >> v[i];
    
    nextv = vector<ll>(n + 2, 0);
    nextv[n + 1] = n + 1;
    vector<ll> mp(100010, -1);

    for(ll i = n; i >= 1; i--)
    {
        nextv[i] = i + 1;
        ll pos = n + 1;
        for(auto j : primeFactors(v[i]))
        {
            if(mp[j] != -1)
                pos = min(pos, mp[j]);
            mp[j] = i;
        }
        nextv[i] = max(nextv[i], pos);
        nextv[i] = min(nextv[i], nextv[i + 1]);
    }
    
   h = log2(n) + 1;
   nexth = vector<vector<ll>>(n + 2, vector<ll>(h, n + 1));
   for(ll i = n; i >= 1; i--)
   {
       nexth[i][0] = nextv[i];
       for(ll j = 1; j < h; j++)
       {
           nexth[i][j] = nexth[nexth[i][j - 1]][j - 1];
       }
   }

    while(q--)
    {
        ll l, r;
        cin >> l >> r;
        ll lo = 1, hi = n;
        while(lo < hi)
        {
            ll mid = lo + (hi - lo) / 2;
            if(advance(l, mid) > r)
            {
                hi = mid;
            }
            else
            {
                lo = mid + 1;
            }
        }
        cout << lo << endl;
    }

    return 0;
}


