#include <bits/stdc++.h> using namespace std; const int N=1e5+5; int t; struct R{ int n,id; }a[N]; int ans[N]; 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; } bool cmp(R x,R y){ return x.n<y.n; } bool f[100000004]; int main(){ t=read(); for(register int i=1;i<=t;i++){ a[i].n=read(); a[i].id=i; } sort(a+1,a+t+1,cmp); for(register int i=2;i<=10000;i++){ f[i*i]=1; int p=i*i; for(register int j=2;p*j<=100000000;j++){ f[p*j]=1; } } int j=1,cnt=0; for(register int i=1;i<=100000000;i++){ if(f[i]) cnt++; if(a[j].n==i){ ans[a[j].id]=cnt; j++; } } for(int i=1;i<=t;i++){ printf("%d\n",ans[i]); } return 0; }