#include <bits/stdc++.h>
using namespace std;

using u64 = uint_fast64_t;

u64 count_primes(const u64 n) {
	auto v = (unsigned int)sqrt(n);
	vector<u64>			 higher(v + 2, 0);
	vector<unsigned int> lower(v + 2, 0);
	vector<bool>		 used(v + 2, false);
	u64 result = n - 1;
	for (unsigned int p = 2; p <= v; p++) {
		lower[p] = p - 1;
		higher[p] = n / p - 1;
	}
	for (unsigned int p = 2; p <= v; p++) {
		if (lower[p] == lower[p - 1]) continue;
		auto temp = lower[p - 1];
		result -= higher[p] - temp;
		auto pxp = (u64) p * p;
		auto end = min<u64>(v, n / pxp);
		auto j = 1 + (p & 1);
		for (auto i = p + j; i <= end + 1; i += j) {
			if (used[i]) continue;
			auto d = i * p;
			if (d <= v) higher[i] -= higher[d] - temp;
			else 		higher[i] -= lower[n / d] - temp;
		}
		for (auto i = v; i >= pxp; i--) lower[i] -= lower[i / p] - temp;
		for (auto i = pxp; i <= end; i += p * j) used[i] = true;
	}
	return result;
}


int main() {
	u64 a, b;
	cin >> a;
	while (a--) {
		cin >> b;
		cout << count_primes(b) << '\n';
	}
}