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

#define Fio                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr)
////////// 	Template structure for debugging
#define tr(...) trace(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void trace(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void trace(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cout.write(names, comma-names) << " : " << arg1 << " | " ;
trace(comma+1, args...);
}
#define print(...) pr(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void pr(const char* name, Arg1&& arg1){
cout << arg1 << endl;
}
template <typename Arg1, typename... Args>
void pr(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cout << arg1 << " ";
pr(comma+1, args...);
}

void printV(vector<int> &arr)
{
	cout << "Vector : ";
	for(int i=0;i<arr.size();i++)
		cout << arr[i] << " \n"[ i == arr.size()-1 ];
}
void printA(int arr[], int n)
{
	cout << "Array : ";
	for(int i=0;i<n;i++)
		cout << arr[i] << " \n"[ i == n-1 ];
}
//----------- prime factorization of a number N
	//vector<int> factorize(int N){
		//for(ll i=2; i*i <=N; i++){
		//if(N % i)continue;
		//factors.push_back(i);
		//while(N % i == 0)N /= i;
		//}
		//if(N > 1)factors.push_back(q1);

		//return factors
	//}
//-----------power for a ^ b
	//int power(int a, int b){
		//int ans = 1;
		//while(b){
		 //if(b&a)ans *= a;
		 //a *= a;
		 //b >>= 1;
		//}
		//return ans
	//}
//-----------factorial of a number n
//int fact(int n){
	//int ans = 1;
	//for(int i=1; i<=n; i++)ans = 1ll * ans * i % MOD;
	//return ans;
//}
//-----------N C r
//int ncr(int n, int r){
	//if(r > n)return 0;
	//if(r==0 || n==0)return 1;
	//if(r==1)return n;
	//int a = fact(n), b = 1ll * fact(n-r) % MOD, c = 1ll * fact(r) % MOD;
	//int ans = 1ll * a * power(b, MOD-2) % MOD;
	//ans = 1ll * ans * power(c, MOD-2) % MOD;
	//return ans;
//}
//------------------sieve of eratosthenes
//
//arr[0] = 1;
//arr[1] = 1;
//for(int i=2; i*i <= N; i++){
	//if(!arr[i]){
		//for(int j=i*i; j<=N; j++)
			//arr[j] = 1;
	//}
//}

#define ll long long int;
const int N = 1e6+1;
int arr[N];
int main(){
    Fio;
	for(int i=0; i<=N; i++)arr[i] = 1;
	arr[0] = 0;
	arr[1] = 0;

	for(int i=2; i*i <= N; i++){
		if(arr[i]){
			for(int j=i*i; j<=N; j+=i)
				arr[j] = 0;
		}
	}
	for(int i=3; i<=N; i++)arr[i] += arr[i-1];

	int t;
	cin >> t;
	while(t--){
		int num;
		cin >> num;
		int sq = sqrt(num);
		//tr(arr[num], arr[sq],N, num, sq);
		cout << arr[num] - arr[sq] + 1 << "\n";
	}
}