#include"iostream"
using namespace std;
int main()
{
	int cn;
	cin>>cn;
	while(cn--){
		int sum=1,n;
		cin >> n;
		if(n<3){
			cout << "0" << endl;
			continue;
		}
		int ys[40000]={0},jl=0;
		for(int i=2;i<n;i++){
			if(n%i==0){
				ys[jl++]=i;
			}
		}
		for(int i=2;i<n;i++){
			int pd=0;
			for(int j=0;j<jl;j++){
				if(i<ys[j]){
					sum++;
					break;
				}
				if(i%ys[j]==0){
					break;
				}
				else pd++;
			}
			if(pd>=jl){
				sum++;
			}
		}
		cout << sum << endl;
	}
	return 0;
}