#include <bits/stdc++.h>
using namespace std;
int a[1000100], a1[1000100];
void solve() {
  a1[1] = 1;
  for (int i = 2; i <= 1000010; i++) {
    if (!a[i]) {
      for (int j = i * 2; j <= 1000010; j += i) {
        a[j] = 1;
      }
    }
    if (a[i] == 0) {
      a1[i] = a1[i - 1] + 1;
    } else
      a1[i] = a1[i - 1];
  }
}
int main() {
  solve();
  int n;
  scanf("%d", &n);
  while (n--) {
    int t;
    scanf("%d", &t);
    int k = sqrt((double)t);
    printf("%d\n", a1[t] - a1[k] + 1);
  }
}
