#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
int isprime(int n){
    int i,limit,flag=1;
	if(n<=1)
		flag=0;
	else if(n==2)
		flag=1;
	else if(n%2==0)
		flag=0;
	else{
	    limit=(sqrt)(n*1.00)+1;
		for(i=3;i<=limit;i+=2){
			if(n%i==0){
			  flag=0;
			  break;
			}
		}
	}
	return flag;
}
int main(){
	int t;
   scanf("%d",&t);
   while(t--){
	   int j,a,b=0;
      scanf("%d",&a);
	  if(a<13){
	     for(j=2;j<=a;j++){
		   if(isprime(j)){
		      b++; 
		   }
		 }
	  }
	  if(a>=13){
	   for(j=13;j<=a;j++){
		   if(j%2!=0&&j%3!=0&&j%5!=0&&j%7!=0&&j%11!=0&&isprime(j)){
		      b++; 
		   }
	   }
	   b+=5;
	  }
      printf("%d\n",b);
   }
}