求素数  然后容斥原理 // n之内有平方因子的数的个数sum =n/(2^2) + n/(3^2)+……+n/(k^2) - n/(2^2 * 3^2)-……+…….

 

// #pragma comment(linker, "/STACK:1024000000,1024000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define MOD 1000000007#define maxn 1000010#define maxm 1000010#define LL long longLL pr[maxn];int p;void getprime(){ int i,j; for(i=4;i
            
             m) return; if(dep%2) sum+=n/(tp*tp); else sum-=n/(tp*tp); dfs(i+1,dep+1,tp); }}int main(){ getprime(); int T; scanf("%d",&T); while(T--){ // scanf("%I64d",&n); scanf("%lld",&n); m=sqrt(n+1.0); sum=0; dfs(0,1,1); // printf("%I64d\n",n-sum); printf("%lld\n",n-sum); }}