#include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=1e8+8; int t; int n; int ans[M]; inline int read(){ int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x; } int f[M]; int main(){ t=read(); for(register long long i=2;i<=10000;i++){ f[i*i]=1; long long p=i*i; for(register int j=2;p*j<M;j++){ f[p*j]=1; } } for(int i=1;i<M;i++){ ans[i]=ans[i-1]+f[i]; } for(register int i=1;i<=t;i++){ n=read(); printf("%d\n",ans[n]); } return 0; }