#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline void boostIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
}
bool isPrime(int x) {
  if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  for (int i = 5; i * i <= x; i += 6)
    if (x % i == 0 || x % (i + 2) == 0) return 0;
  return 1;
}
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int lcm(long long int a, long long int b) {
  return a * b / gcd(a, b);
}
template <typename T>
inline T getint() {
  T val = 0;
  char c;
  bool neg = false;
  while ((c = getchar()) && !(c >= '0' && c <= '9')) {
    neg |= c == '-';
  }
  do {
    val = (val * 10) + c - '0';
  } while ((c = getchar()) && (c >= '0' && c <= '9'));
  return val * (neg ? -1 : 1);
}
int Mod = 1e9 + 7;
long long int inf = 2e18;
int32_t main() {
  boostIO();
  vector<int> A(1e6 + 101, 1);
  for (int i = 2; i <= 1e6 + 100; ++i) {
    if (A[i] == 0) continue;
    for (int j = i + i; j <= 1e6 + 100; j += i) {
      A[j] = 0;
    }
  }
  vector<int> Primes;
  for (int i = 2; i <= 1e6 + 100; ++i) {
    if (A[i] == 1) Primes.push_back(i);
  }
  int l = 0;
  int r = 0;
  vector<int> Ans(1e6 + 101, 1);
  for (long long int i = 2; i <= 1e6; ++i) {
    while (Primes[r + 1] <= i) {
      ++r;
    }
    while (1ll * Primes[l] * Primes[l] <= i) ++l;
    Ans[i] += r - l + 1;
  }
  int T;
  cin >> T;
  while (T--) {
    int x;
    cin >> x;
    cout << Ans[x] << '\n';
  }
  cerr << '\n' << "RUNTIME: " << 1.0 * clock() / CLOCKS_PER_SEC << " s" << '\n';
  return 0;
  ;
}
