func_code_string: #include <bits/stdc++.h>   using namespace std;   int n,q,a[100005],np[100005],cnt[100005],nx[19][100005],p1,p2;   vector<int> p,fac[100005];   bool check(int ind) {       for (int i=0; i<fac[ind].size(); i++) {           if (cnt[fac[ind][i]]) return 0;       }       for (int i=0; i<fac[ind].size(); i++) cnt[fac[ind][i]]++;       return 1;   }   void rem(int ind) {       for (int i=0; i<fac[ind].size(); i++) {           cnt[fac[ind][i]]--;       }   }   void fun() {       int l=0,r=0;       while (l<n) {           while (r<n and check(r)) r++;           nx[0][l]=r;           rem(l); l++;       }       nx[0][n]=n;       for (int i=1; i<19; i++) {           for (int j=0; j<=n; j++) {               nx[i][j]=nx[i-1][nx[i-1][j]];           }       }   }   int getans(int l,int r) {       int ind=18,ret=0,cur=l;       while (ind>=0) {           if (nx[ind][cur]<=r) {               ret+=(1<<ind); cur=nx[ind][cur];           }           ind--;       }       return ret+1;   }   int main() {       for (int i=2; i<=1e5; i++) {           if (np[i]) continue;           p.push_back(i);           for (int j=2*i; j<=1e5; j+=i) {               np[j]=1;           }       }       cin>>n>>q;       for (int i=0; i<n; i++) cin>>a[i];       for (int i=0; i<n; i++) {           int ind=0,x=a[i];           while (p[ind]<318) {               bool s=0;               while (x%p[ind]==0) {                   x/=p[ind]; s=1;               }               if (s) fac[i].push_back(p[ind]);               ind++;           }           if (x!=1) {               fac[i].push_back(x);           }       }       fun();       for (int i=0; i<q; i++) {           cin>>p1>>p2; p1--; p2--;           cout<<getans(p1,p2)<<  n ;       }   }