#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int ans[maxn];
int cnt = 0;
bool vis[maxn];
int prime[maxn];
void get_prime() {
  int up = 1e6;
  memset(vis, 0, sizeof(vis));
  vis[1] = 1;
  for (int i = 2; i <= up; i++) {
    if (!vis[i]) prime[++cnt] = i;
    for (int j = 1; j <= cnt && i * prime[j] <= up; j++) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
void init() {
  for (int i = 1; i <= cnt; i++) {
    int x = prime[i];
    long long y = 1ll * x * x;
    ans[x]++;
    if (y <= 1e6) ans[y]--;
  }
  ans[0] = 1;
  for (int i = 1; i <= 1e6; i++) ans[i] += ans[i - 1];
}
int main() {
  std::ios::sync_with_stdio(false), cin.tie(0);
  get_prime();
  init();
  int T;
  cin >> T;
  while (T--) {
    int x;
    cin >> x;
    cout << ans[x] << '\n';
  }
  return 0;
}
