#include <bits/stdc++.h>
using namespace std;
bool prime[1 << 20];
int PRIME[1 << 20];
int main() {
  for (int i = 0; i < (1 << 20); i++) prime[i] = 1;
  for (int i = 2; i <= 1000; i++) {
    if (prime[i]) {
      for (int j = i * i; j <= 1000000; j += i) {
        prime[j] = 0;
      }
    }
  }
  for (int i = 1; i <= 1000000; i++) {
    PRIME[i] = PRIME[i - 1] + prime[i];
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    int answer = 1;
    printf("%d\n", 1 + PRIME[n] - PRIME[(int)(sqrt(n))]);
  }
  return 0;
}
