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