//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")

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

#define fast_io         {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#define all(v)          v.begin(),v.end()
#define pb              push_back
#define bs              binary_search
#define popb            pop_back
#define F               first
#define S               second
#define ccc             cout<<1<<" ";
#define prin(v)         {for(auto u : v) cout << u << " "; cout << endl;}
#define forn(i,n)       for(int i=0;i<(n);i++)
#define len()           length()

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<bool> vbool;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1e9 + 7;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int N = 1e5 + 10;
ifstream fin("test.txt");


int main()
{
    fast_io;

    int n, q; cin >> n >> q;
    vint v(n), nex(N);
    forn(i,n) cin >> v[i];

    vector < vint > prime(N);
    for(int i = 2; i < N; i++)
    {
        for(int j = i; j < N; j += i)
            prime[j].pb(i);
        nex[i] = n + 1;
    }

    vector < vint > dp(20, vint(n + 10, n + 1));

    for(int i = n-1; i >= 0; i--)
    {
        int sl = n + 1;
        for(auto u : prime[v[i]])
        {
            sl = min(sl, nex[u]);
            nex[u] = i;
        }
        sl = min(sl, dp[0][i+1]);
        dp[0][i] = sl;
    }

    for(int q = 1; q < 20; q++)
    {
        for(int i = n - 1; i >= 0; i--)
        {
            dp[q][i] = dp[q-1][dp[q-1][i]];
        }
    }

    forn(i,q)
    {
        int l, r; cin >> l >> r;
        l--; r--;
        int ans = 0, cur = l;

        while(cur <= r){
            for(int i = 19; i >= 0; i--)
            {
                if(dp[i][cur] <= r){
                    ans += (1 << i);
                    cur = dp[i][cur];
                    continue;
                }
            }
            ans++;
            break;
        }
        cout << ans << endl;
    }
}




















