# include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr double eps=1e-8;
ll solve(ll n)
{
	int sqn=sqrtl(n),m=0,tot=0;
	static int prime[400010];
	static ll blo[700010],f[700010];
	static bool npri[400010];
	npri[1]=1;
	for(int i=2;i<=sqn;i++)
	{
		if(!npri[i]) prime[++m]=i;
		for(int j=1;j<=m && i*prime[j]<=sqn;j++)
		{
			npri[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
	for(ll i=1,j;i<=n;i=j+1) j=n/(n/i),blo[++tot]=n/i;
	auto getid=[&](ll x)->int{return x<=sqn?tot-x+1:n/x;};
	for(int i=1;i<=tot;i++) f[i]=blo[i]-1;
	for(int i=1;i<=m;i++)
	{
		double inv=1./prime[i];
		for(int j=1;j<=tot && blo[j]>=(ll)prime[i]*prime[i];j++)
			f[j]-=f[getid(blo[j]*inv+eps)]-i+1;
	}
	ll ans=n-(n-1-(f[getid(n)]-f[getid(n/2)]))/2;
	memset(prime+1,0,sizeof(int)*m);
	memset(blo+1,0,sizeof(ll)*tot);
	memset(f+1,0,sizeof(ll)*tot);
	memset(npri+1,0,sizeof(bool)*sqn);
	return ans;
}
int main()
{
	int T;
	ll n;
	cin>>T;
	while(T--) scanf("%lld",&n),printf("%lld\n",solve(n));
	return 0;
}