[Baekjoon] #6359 만취한 상범

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		
		Scanner sc = new Scanner(System.in);
		
		int tc = sc.nextInt();
		
		for(int i=0;i<tc;i++){
			
			int n = sc.nextInt();
			int cnt =0;
			int[] dp = new int[n+1];
			
			
			for(int j=2;j<=n;j++){
				for(int k=1;k<=n;k++){
					if(j*k > n)continue;
					if(dp[j*k]==0){
						dp[j*k]=1;
					}else if(dp[j*k]==1){
						dp[j*k]=0;
					}
				}
			}
			
			for(int j=1;j<=n;j++){
				if(dp[j] == 0){
					cnt++;
				}
			}
			System.out.println(cnt);
		}
	}
}