func_code_string: #include<bits/stdc++.h>   #define ll long long   #define ri register int   #define lowbit(x) x&(-x)   #define lson rt<<1, l, mid   #define rson rt<<1|1, mid+1, r   using namespace std;   const int p = 1e9+7;   const int maxn = 4e5+10;   int n, m, t, q;   int a[maxn], vis[maxn], go[maxn], two;   int dp[maxn][30];   void divide(int x, int k){    int t = sqrt(x);    for(int i = 2;i <= t;i ++){     if(x%i == 0){      vis[i] += k;      if(vis[i] == 1 && k == -1) two --;      else if(vis[i] >= 2) two ++;      while(x%i == 0) x /= i;     }    }    if(x > 1){     vis[x] += k;     if(vis[x] == 1 && k == -1) two --;     else if(vis[x] >= 2) two ++;    }   }   int main(){    scanf( %d%d ,&n,&q);    for(int i = 1;i <= n;i ++)     scanf( %d ,&a[i]);    int l = 1, r = 0;    while(r < n){     r ++;     divide(a[r], 1);     if(two){      go[l] = r;      while(two){       divide(a[l], -1);       l ++;       go[l] = r;      }     }    }    for(int i = l;i <= n+1;i ++)     go[i] = n+1;    for(int i = 1;i <= n;i ++){     dp[i][0] = go[i];    }    for(int j = 1;j <= 20;j ++)     for(int i = 1;i <= n+1;i ++){      if(dp[dp[i][j-1]][j-1])       dp[i][j] = dp[dp[i][j-1]][j-1];      else dp[i][j] = n+1;     }    for(int i = 1;i <= q;i ++){     int l, r;     ll ans = 0;     scanf( %d%d ,&l,&r);     for(int j = 20;j >= 0;j --){      //cout << l <<     << j <<     << dp[l][j] << endl;      if(dp[l][j] <= r){       l = dp[l][j];       ans += 1ll<<j;      }     }     printf( %lld n ,ans+1);    }    return 0;   }