#include <bits/stdc++.h>
const int N = 1010000;
int f[N], n, m, sum[N];
int main() {
  f[1] = 1;
  scanf("%d", &m);
  for (int i = 2; i <= 1000000; ++i) {
    if (!f[i]) {
      for (int j = 2; 1ll * i * j <= 1000000; ++j) {
        f[i * j] = 1;
      }
    }
  }
  for (int i = 1; i <= 1000000; ++i) sum[i] = sum[i - 1] + (!(f[i] >= 1));
  while (m--) {
    scanf("%d", &n);
    int tmp = sqrt(n);
    int ans = sum[n] - sum[tmp];
    printf("%d\n", ans + 1);
  }
  return 0;
}
