//make up a table of prime factors
#include <stdio.h>
#include <stdlib.h>
#define MAX 32769
/* run this program using the console pauser or add your own getch, system("pause") or input loop */int main(int argc, char *argv[]) {
int Prime[MAX];
int n,sum,t;
int i,j;
scanf("%d",&t);
while( t-- && (scanf( "%d" , &n ) != EOF) ) {
for( i = 0 ; i <= n ; i++ ) {
Prime[i] = 0 ;
}
sum = 0;
for( i = 2 ; i <= n ; i++ ) {
if( (n%i == 0) && (Prime[i] == 0) )
for( j = i ; j <= n ; j += i ) {
Prime[j] = 1 ;
}
}
for( i = 1 ; i <= n ; i++) {
if( Prime[i] == 0 ) {
sum += 1;
}
}printf("%d\n",sum);}return 0;
}