func_code_string: #pragma GCC optimize( Ofast )   #include  bits/stdc++.h    typedef long long ll;   using namespace std;       #define sim template < class c    #define ris return * this    #define dor > debug & operator <<    #define eni(x) sim > typename    enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {    sim > struct rge { c b, e; };    sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }    sim > auto dud(c* x) -> decltype(cerr << *x, 0);    sim > char dud(...);    struct debug {      // #ifdef LOCAL     ~debug() { cerr << endl; }     eni(!=) cerr << boolalpha << i; ris; }     eni(==) ris << range(begin(i), end(i)); }     sim, class b dor(pair < b, c > d) {      ris <<  (  << d.first <<  ,   << d.second <<  ) ;     }     sim dor(rge<c> d) {      *this <<  [ ;      for (auto it = d.b; it != d.e; ++it)       *this <<  ,   + 2 * (it == d.b) << *it;      ris <<  ] ;     }         // sim dor(const c&) { ris; }    };    #ifdef ASJKD   }    #endif    #define imie(...)   [  << #__VA_ARGS__  :   << (__VA_ARGS__) <<  ]      #define read(x) for(auto &i : (x)){cin>>i;}    #define all(x) begin(x), end(x)    #define pb push_back    #define pii pair<int,int>   #define maxn 100005   ll mod = 1e9+7;   int INF = 1e9+1e8+1e7;   ll INF64 = 1e18;      long long binpow(long long a, long long b, long long m) {    a %= m;    long long res = 1;    while (b > 0) {     if (b & 1){      res = res * a % m;     }     a = a * a % m;     b >>= 1;    }    return res;   }   vector<vector<int>> pfs(maxn);   vector<bool> isprime(maxn, 1);   void sieve(int mx){    for(int i=2;i<mx;i++){     if(isprime[i]){      for(int j=i;j<mx;j+=i){       isprime[j]=0;       pfs[j].pb(i);      }     }     }   }   void test_case(int tnum){    int n,q;    cin>>n>>q;    vector<int> a(n);    read(a);    vector<int> go(n+1, n);    vector<int> last(maxn, n);    for(int i=n-1;i>=0;i--){     for(int j : pfs[a[i]]){      go[i]=min(go[i], last[j]);      last[j] = min(last[j], i);     }     go[i] = min(go[i], go[i+1]);    }    // debug() << imie(go);    vector<vector<int>> lift(20, vector<int>(n+1, n));    for(int i=0;i<n;i++){     lift[0][i] = go[i];    }    for(int i=1;i<20;i++){     for(int j=0;j<n;j++){      lift[i][j]=lift[i-1][lift[i-1][j]];     }    }    for(int rep=0;rep<q;rep++){     int l, r;     cin>>l>>r;     --l,--r;     int cur=l;     int ans =0;      while(true){      if(go[cur] > r){       ans++;       break;      }      for(int i=19;i>=0;i--){       if(lift[i][cur]<=r){        ans += 1<<(i);        cur = lift[i][cur];        break;       }      }     }     cout<<ans<<  n ;    }   }      int main(){    cin.tie(0);    cout.tie(0);    ios_base::sync_with_stdio(false);    int t=1;    sieve(maxn);    // cin>>t;    for(int test=1;test<=t;test++){     test_case(test);    }    return 0;   }