#include <bits/stdc++.h>
using namespace std;
int a[1000010], b[1000010];
int main() {
  int i, j, k, n, m, x, y, z, t;
  n = 1000000;
  for (i = 2; i <= n; i++) {
    if (a[i] == 0) {
      for (j = i * 2; j <= n; j += i) {
        a[j] = 1;
      }
    }
  }
  a[1] = 1;
  for (i = 1; i <= n; i++) {
    b[i] = b[i - 1] + (1 ^ a[i]);
  }
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    printf("%d\n", b[n] - b[(int)sqrt(n)] + 1);
  }
}
