#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <chrono> 
// using namespace std::chrono; 
// using namespace __gnu_pbds;

 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void print(T t, V... v) {_print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define ff              first
#define ss              second
#define int             long long
#define double          long double
#define pb              push_back
#define mp              make_pair
#define pi              pair<int,int>
#define vtiii           vector<tuple<int,int,int>>
#define vi              vector<int>
#define vpii            vector<pair<int,int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int>>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define inf             1e18  
// #define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define all(x) (x).begin(), (x).end()
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) 
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
const int mxN = 2e5 + 10;
const int mod = 1e9 + 7;

vi primefac(1e5 + 5 , -1);

void precalc(){
    for(int i=2;i<1e5+5;++i){
        if(primefac[i] == -1){
            for(int j=i;j<1e5+5;j+=i){
                primefac[j] = i;
            }
        }
    }
}

int bl(vector<vi> &dp , int l , int m){
    int i = 0 , x = l;
    while(m){
        if(x==inf) return x;
        if(m&1){
            x = dp[i][x];
        }
        m>>=1;
        ++i;
    }
    return x;
}

void solve(){
    int n,q;cin>>n>>q;
    vi v(n+1) , go(n+1 , inf);
    for(int i=1;i<=n;++i) cin>>v[i];
    map<int,int> M;
    int x = v[n];
    if(x != 1){
        while(x != primefac[x]){
            int fac = primefac[x];
            M[fac] = n;
            x/=fac;
        }
        M[x] = n;
    }

    set<int> seen;
    for(int i=n-1;i>=1;--i){
        seen.clear();
        go[i] = go[i+1];
        int x = v[i];
        if(x != 1){
            while(x != primefac[x]){
                int fac = primefac[x];
                if(M.find(fac) != M.end()){
                    go[i] = min(go[i] , M[fac]);
                }
                seen.insert(fac);
                x/=fac;
            }
            if(M.find(x) != M.end()){
                go[i] = min(go[i] , M[x]);
            }
            M[x] = i;
            for(int num : seen) M[num] = i;
        }
    }
    vector<vi> dp(20,vi(n+1));
    for(int i=1;i<=n;++i){
        dp[0][i] = go[i];
    }
    for(int i=1;i<20;++i){
        for(int j = 1 ; j<=n ; ++j){
            int l = dp[i-1][j];
            if(l != inf)dp[i][j] = dp[i-1][l];
            else dp[i][j] = inf;
        }
    }
    while(q--){
        int l,r; 
        cin>>l>>r;
        int s = 0 , e = n , m , p;
        while(s<=e){
            m = (s+e)/2;
            if(bl(dp,l,m) > r){
                p = m;
                e = m-1;
            }else{
                s = m + 1;
            }
        }
        cout<<p<<endl;
    }
}
                                                                                                            
int32_t main(){
    // auto start = high_resolution_clock::now();
    FIO;
    #ifndef ONLINE_JUDGE
        freopen("input.in", "r", stdin);
        freopen("output.in", "w", stdout);
    #endif
    precalc();
    // w(x)                          
    solve(); 
    // auto stop = high_resolution_clock::now(); 
    // auto duration = duration_cast<microseconds>(stop - start); 
    // cout << duration.count() << endl;
}