#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
bool prime[N];
int prefix[N], n, t, temp;
int main() {
  for (int i = 2; i < N; i++) {
    if (!prime[i]) {
      for (int j = i + i; j < N; j += i) {
        prime[j] = 1;
      }
    }
    prefix[i] += prefix[i - 1] + (1 ^ prime[i]);
  }
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    temp = sqrt(n);
    printf("%d\n", prefix[n] - prefix[temp] + 1);
  }
  return 0;
}
