#include <bits/stdc++.h> using namespace std; #define mod 998244353 inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=x*10+ch-48; ch=getchar(); } return x*f; } template<typename T> inline void write(T X) { if(X<0) { putchar('-'); X=~(X-1); } int s[50],top=0; while(X) { s[++top]=X%10; X/=10; } if (!top) s[++top]=0; while(top) putchar(s[top--]+'0'); putchar('\n'); return; } int ans[5001],n,T; int main() { // freopen("pair.in","r",stdin); // freopen("pair.out","w",stdout); T=read(); for(int i=1; i<=5000; i++) { ans[i]=ans[i-1]; for(int j=2; j*j<=i; j++) if(!(i%(j*j))) { ans[i]++; break; } } while(T--) { n=read(); write(ans[n]); } return printf("\n"),0; }