#include <bits/stdc++.h> using namespace std; const int maxn=1e7+1; int ans[maxn],T,n; void Init() { for(int i=2; i*i<=maxn; i++)for(int j=1; i*i*j<=maxn; j++)ans[i*i*j]=1; for(int i=1; i<=maxn; i++) ans[i]+=ans[i-1]; } int main() { Init(); cin>>T; while(T--) { cin>>n; cout<<ans[n]<<endl; } return 0; }