// nauynix
// 27/04/2021
#include <bits/stdc++.h>
using namespace std;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef long long int  ll;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int nxt() {int x;cin >> x;return x;}

int n, lng;
VI g;

ll _sieve_size;
bitset<10000010> bs;  
VI primes;            

void sieve(ll upperbound) {        
    _sieve_size = upperbound + 1;  
    bs.set();                      
    bs[0] = bs[1] = 0;             
    for (ll i = 2; i <= _sieve_size; i++)
        if (bs[i]) {
            for (ll j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
            primes.push_back((int)i);  
        }
}
VI primeFactors(ll N) {                  
    VI factors;                          
    ll PF_idx = 0, PF = primes[PF_idx];  
    while (N != 1 && (PF * PF <= N)) {   
        while (N % PF == 0) {
            N /= PF;
            factors.push_back(PF);
        }                       
        PF = primes[++PF_idx];  
    }
    if (N != 1) factors.push_back(N);  
    return factors;                    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    n = nxt();
    int q = nxt();
    lng = ceil(log2(n));
    g.assign(n, 0);
    VI a(n);
    generate(all(a), nxt);
    sieve(1e5);
    int j = 0;
    set<int> s;
    for (int i = 0; i < n; i++) {
        if (i) {
            VI p = primeFactors(a[i-1]);
            for (int x : p) s.erase(x);
        }
        while (j < n) {
            VI p = primeFactors(a[j]);
            bool t = true;
            for (int x : p) if (s.count(x)) t = false;
            if (t) {
                j++;
                for (int x : p) s.insert(x);
            } else {
                break;
            }
        }
        g[i] = j;
        // at the end: [i, j)
    }
    VVI up(n+1, VI(lng+1));
    rep (i, 0, n) {
        up[i][0] = g[i];
    }
    up[n][0] = n;
    /* for (int x : g) printf("%d ", x); */
    /* puts(""); */
    for (int i = 1; i <= lng; i++) {
        rep (v, 0, n+1) {
            up[v][i] = up[up[v][i-1]][i-1];
            /* printf("%d ", up[v][i]); */
        }
        /* puts(""); */
    }
    while (q--) {
        int l = nxt(), r = nxt();
        l--,r--;
        int low = 1, high = r-l+1;
        while (low < high) {
            int m = (low + high) / 2;
            int cur = l;
            for (int j = 0; j <= lng; j++){
                /* printf("%d %d %d\n", j, m, (1<<j) & m); */
                if ((1<<j) & m) {
                    cur = up[cur][j];
                }
            }
            /* printf("%d %d\n", m, cur); */
            if (cur <= r) {
                low = m+1;
            } else high = m;
        }
        printf("%d\n", low);
    }
    return 0;
}

