#include<bits/stdc++.h>
using namespace std;
bool vt[6145140];
int pri[6145140],n;
int main(){
	int m,k=0;cin>>m;
	for(int i=2;i<=6000005;i++){
		if(vt[i]==0) pri[k++]=i;
		for(int j=0;j<=k;j++){
			if(i*pri[j]>6000005) break;
			vt[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>n;
		for(int j=0;j<=k;j++){
			if(pri[j]>n){
				cout<<j<<" ";
				break;
			} 
		}
	}
}