#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>conto(100002);
int ancestor[100002][20];
void init(){
    int tmem = 0;
    vector<bool>is_prime(100002,true);
    for(int i = 2; i < 100002; ++i){
        if(is_prime[i])
            for(int j = i; j < 100002;j +=i){
                conto[j].push_back(i);
                is_prime[j] = false;
            }
    }
}
void solve(){
    int n,q;
    cin >> n >> q;
    vector<int>arr(n);
    for(int & i : arr) cin >> i;
    vector<int>last_pos(100002,n);
    vector<int>nxt(n);
    for(int i = n - 1; i >= 0; --i){
        int nxtpos = n;
        //assert(i >= 0);
        //assert(conto[arr[i]].size());
        for(int k : conto[arr[i]]){
            nxtpos = min(nxtpos,last_pos[k]);
        }
        if(i < n - 1){
            nxtpos = min(nxtpos,nxt[i+1]);
        }
        nxt[i] = nxtpos;
        for(int k : conto[arr[i]]){
            last_pos[k] = i;
        }
    }
    /*for(int i = 0; i < n; ++i){
        cerr << nxt[i] << " ";
    }
    cerr << "\n";*/
    for(int i = 0; i < n; ++i){
        ancestor[i][0] = nxt[i];
        //cerr << ancestor[i][0] << " ";
    }
    //cerr << "\n" ;
    for(int i = 0; i < 19; ++i){
        ancestor[n][i] = n;
    }
    for(int i = 0; i < 18; ++i){
        for(int j = 0; j < n; ++j){
            ancestor[j][i+1] = ancestor[ancestor[j][i]][i];
            //if(!i) cerr << ancestor[j][i] << " -> " << ancestor[ancestor[j][i]][i] << " ";
        }
    }
    /*cerr << "\n";
    for(int i = 0;i < n; ++i){
        assert(ancestor[i][0] == nxt[i]);
        for(int j = 0; j < 10; ++j){
            cerr << ancestor[i][j] << " ";
        }
        cerr << "\n";
    }*/
    auto go = [&](int pos, int h){
        //cerr << pos << " to "<< h << "\n";
        for(int i = 0; i < 19; i ++){
            if(h & (1 << i)){
                //cerr <<  "going up by " << (1 << i) << "from " << pos <<"\n"; 
                assert(pos <= n && pos >= 0);
                assert(i >= 0 && i < 20);
                //cerr << ancestor[pos][i] << "\n";
                pos = ancestor[pos][i];
                //cerr << "pos \n";
            }
        }
        return pos;
    };
    while(q--){
        int l,r;
        cin >> l >> r;
        l--;r--;
        int low = 1;
        int high = n - l;
        while(low < high){
            int mid = low + (high - low)/2;
            //cerr << low << " , "<< mid << " , "<< high << "\n";
            if(go(l,mid) > r){
                high = mid;
            }
            else{
                low = mid + 1;
            }
        }
        cout << low << "\n";
    }
}
int main(){
    int t;
    t = 1;
    init();
    while(t--){
       solve();
    }
}