#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int p[N], a[N], idx, pre[N];
void xxs() {
  int kns = 0;
  for (int i = 2; i <= N; i++) {
    if (!a[i]) {
      p[++idx] = i;
      kns++;
    }
    for (int j = 1; j <= idx && i * p[j] <= N; j++) {
      a[i * p[j]] = 1;
      if (i % p[j] == 0) break;
    }
    pre[i] = kns;
  }
}
int main() {
  xxs();
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    int k = sqrt(n);
    printf("%d\n", pre[n] - pre[k] + 1);
  }
  return 0;
}
