#include <bits/stdc++.h>
int prime[1000000], nprime;
int min_factor[15000000];
void euler_sieve() {
  for (int i = 2; i < 15000000; ++i) {
    if (!min_factor[i]) prime[nprime++] = i, min_factor[i] = i;
    for (int j = 0; i * prime[j] < 15000000; ++j) {
      min_factor[i * prime[j]] = prime[j];
      if (prime[j] == min_factor[i]) break;
    }
  }
  0;
}
int sqrt(int k) {
  int r = 0;
  for (int i = 1 << 14; i; i >>= 1)
    if ((r + i) * (r + i) <= k) r += i;
  return r;
}
int main() {
  euler_sieve();
  int T;
  scanf("%d", &T);
  for (int tc = 1; tc <= T; ++tc) {
    int n;
    scanf("%d", &n);
    int ans = std::upper_bound(prime, prime + nprime, n) -
              std::upper_bound(prime, prime + nprime, sqrt(n)) + 1;
    printf("%d\n", ans);
  }
  return 0;
}
