#include<bits/stdc++.h>
#define MAX 8000001
#define MAX2 1000001
using namespace std;
typedef long long ll;

vector<int> sieve(MAX);
bool sieveRaw[MAX];
ll A[MAX], B[MAX];
ll N, C, y;
int num[MAX], pri[MAX];

void update(int idx, int value){
	while(idx <= y){
		sieve[idx] = sieve[idx] + value;
		idx = idx + (idx & -idx);
	}
}

int sum(int idx){
	int ret = 0;
	while(idx > 0){
		ret = ret + sieve[idx];
		idx = idx - (idx & -idx);
	}
	return ret;
}

void make_fenwick_tree(){
	for(int i = 2; i <= y; i++){
        sieve[i] += 1;
        if(i + (i & -i) <= y) sieve[i + (i & -i)] += sieve[i];
    }
}

ll s0(ll v){
	if(v <= y) return sum(v);
	return B[N / v]; 
}

void calc_primes(){
	ll i, j;
	for(ll p = 2;p <= C;p++){
		if(sieveRaw[p]) continue;
		ll sp = sum(p - 1);
		ll lim = min(N / y, N / (p * p));
		B[1] -= s0(N / p) - sp;
		for(i = p;i <= lim;i++){
			if(sieveRaw[i]) continue;
			B[i] -= s0(N / (i * p)) - sp;
		}
		j = p * p;
		while(j <= y){
			if(sieveRaw[j]){
				j += p;
				continue;
			}
			sieveRaw[j] = true;
			update(j, -1);
			j += p;
		}
	}
}

void init(){
	ll i;
	for(i = 0;i < MAX;i++) sieve[i] = 0;
	make_fenwick_tree();
	sieveRaw[1] = true;
	for(i = 2;i <= y;i++) sieveRaw[i] = false;
	for(i = 1;i <= C;i++){
		A[i] = i - 1;
		B[i] = N / i - 1;
	}
}

void inn(){
	ll i, j;
	num[1] = 1;
	for(i = 2;i * i < MAX;i++){
		if(num[i]) continue;
		for(j = i * i;j < MAX;j+= i){
			num[j] = 1;
		}
	}
	for(i = 1;i < MAX;i++) pri[i] = pri[i - 1] + !num[i];
}

ll pi(ll n){
	N = n;
	if(N <= 1e6) return pri[N];
	C = sqrt(N);
	y = round(0.7*pow(N, 2.0/3.0) / pow(log(N), 2.0/3.0));
	y = min(y, (ll)4e9);
	y = max(C+1, y);
	init();
	calc_primes();
	return B[1];
}

int main(){
	int T;
	ll n;
	inn();
	scanf("%d", &T);
	while(T--){
		scanf("%lld", &n);
		ll ans = pi(n) - pi(n / 2);
		printf("%lld\n", ans + 1 + (n - ans) / 2);
	}
}