#include <bits/stdc++.h> using namespace std; inline int read(){ int x=0;bool f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();} while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return f?x:-x; } int ans[70005],n,t; int main(){ // freopen("pair.in","r",stdin); // freopen("pair.out","w",stdout); t=read(); for(int i=4;i<=70000;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(); printf("%d\n",ans[n]); } return 0; }