#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
void qread(long long& x) {
  x = 0;
  long long f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
const long long maxn = 1e6 + 100;
long long num = 0;
bool prime[maxn];
long long Prime[maxn];
void make_prime() {
  memset(prime, true, sizeof prime);
  prime[0] = prime[1] = false;
  for (long long i = 2; i < maxn; i++) {
    if (prime[i]) Prime[num++] = i;
    for (long long j = 0; j < num && i * Prime[j] < maxn; j++) {
      prime[i * Prime[j]] = false;
      if (!(i % Prime[j])) break;
    }
  }
}
long long ans[maxn];
void solve() {
  make_prime();
  prime[2] = true;
  queue<long long> q;
  long long num = 1;
  ans[1] = 1;
  for (long long i = 2; i < maxn; ++i) {
    if (prime[i]) {
      ++num;
      q.push(i);
    }
    if (q.front() * q.front() == i) {
      --num;
      q.pop();
    }
    ans[i] = num;
  }
  long long t;
  qread(t);
  while (t--) {
    long long x;
    qread(x);
    printf("%lld\n", ans[x]);
  }
}
int main() {
  solve();
  return 0;
}
