#include<bits/stdc++.h>
using namespace std;
int n,a[10000005],b[10000005],c[10000005],d[10000005];
int main(){
    scanf("%d",&n);
	d[0]=1;
	d[1]=1;
    for(int i = 2;i<=sqrt(1e7);i++){
    	if(d[i]==0){
    		for(int j = i*i;j<=1e7;j+=i){
    			d[j]=1;
    		}
    	}
    }
    for(int i = 1;i<=1000000;i++){
    	c[i]=c[i-1]+!d[i];
    }
    for(int i = 1;i<=n;i++){
    	scanf("%d",&b[i]);
    	if(b[i]==0)cout<<0<<endl;
        else cout<<c[b[i]]<<endl;
    }
    return 0;
}