#include <bits/stdc++.h>
using namespace std;
long long isPrime[1000005];
long long pref[1000005];
void seive() {
  for (long long i = 2; i < 1000005; i++) {
    if (!isPrime[i])
      for (long long j = i + i; j < 1000005; j += i) isPrime[j] = 1;
    pref[i] = pref[i - 1] + 1 - isPrime[i];
  }
}
int main() {
  seive();
  long long t;
  scanf("%lld", &t);
  while (t-- > 0) {
    long long n;
    scanf("%lld", &n);
    long long x = sqrt(n);
    long long ans = pref[n] - pref[x] + 1;
    printf("%lld\n", ans);
  }
  return 0;
}
