#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const int N = 1000005;
long long Power(long long a, long long b) {
  if (b == 0) return 1;
  long long p = Power(a, b / 2);
  p *= p;
  if (b % 2) p *= a;
  return p;
}
const long long MAX_SIZE = 1000001;
vector<long long> isprime(MAX_SIZE, 1);
vector<long long> prime;
vector<long long> SPF(MAX_SIZE);
void manipulated_seive(long long N) {
  isprime[0] = isprime[1] = 0;
  for (long long i = 2; i < N; i++) {
    if (isprime[i]) {
      prime.push_back(i);
      SPF[i] = i;
    }
    for (long long j = 0;
         j < (long long)prime.size() && i * prime[j] < N && prime[j] <= SPF[i];
         j++) {
      isprime[i * prime[j]] = 0;
      SPF[i * prime[j]] = prime[j];
    }
  }
}
vector<long long> v;
long long dp[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  manipulated_seive(MAX_SIZE);
  for (long long i = 0; i < prime.size() && prime[i] <= N; i++)
    v.push_back(prime[i]);
  int t;
  cin >> t;
  while (t--) {
    long long n, ans = 1;
    cin >> n;
    if (n == 1) {
      cout << 1 << '\n';
      continue;
    }
    if (dp[n] != 0) {
      cout << dp[n] << '\n';
      continue;
    }
    long long l = 0, r = (long long)v.size() - 1, m, a = -1, b = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (v[m] * v[m] <= n)
        a = m, l = m + 1;
      else
        r = m - 1;
    }
    l = 0, r = (long long)v.size() - 1;
    while (l <= r) {
      m = (l + r) / 2;
      if (v[m] <= n)
        b = m, l = m + 1;
      else
        r = m - 1;
    }
    if (a != -1)
      ans += (b - a);
    else
      ans += b + 1;
    cout << (dp[n] = ans) << '\n';
  }
  return 0;
}
