#include<stdio.h>
#include<malloc.h>
void main(){
	int m,n,i,j,k;
         int *per;
	scanf("%d",&m);
	for(k=0;k<m;k++){
		scanf("%d",&n);
		per=(int*)malloc((n+1)*sizeof(int));
		for(i=1;i<=n;i++){
			per[i]=0;
		}
		for(i=1;i<=n;i++){
			for(j=i;j<=n;j+=i){
				if(per[j]==0) per[j]=1;
				else per[j]=0;
			}
		}
                  j=0;
		for(i=1;i<=n;i++){
			if(per[i]==1) j++;
		}
		printf("%d\n",j);
		free(per);
	}
}