#include<bits/stdc++.h> using namespace std; int ans[100000005],t,n; int main(){ for(int i=2;i*i<=100000000;i++)for(int j=1;i*i*j<=100000000;j++)ans[i*i*j]=1; partial_sum(ans+1,ans+100000001,ans+1),cin>>t; while(t--)cin>>n,cout<<ans[n]<<'\n'; return 0; }