#include <bits/stdc++.h>
using namespace std;
bool prime[1000009];
vector<long long> pri;
void SieveOfEratosthenes() {
  memset(prime, true, sizeof(prime));
  for (long long p = 2; p * p <= 1000000; p++) {
    if (prime[p] == true) {
      for (long long i = p * p; i <= 1000000; i += p) prime[i] = false;
    }
  }
  for (long long i = 2; i <= 1000000; i++) {
    if (prime[i]) {
      pri.push_back(i);
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  SieveOfEratosthenes();
  while (t--) {
    long long n;
    cin >> n;
    long long counter = 0;
    int i = 0;
    long long sz = pri.size();
    long long st = 0;
    long long end = sz - 1;
    long long idx;
    if (n == 1) {
      printf("1\n");
      continue;
    }
    while (st < end) {
      long long md = st + (end - st) / 2;
      if (pri[md] * pri[md] > n) {
        end = md;
        idx = md;
      } else {
        st = md + 1;
      }
    }
    st = 0;
    end = sz - 1;
    long long id = upper_bound(pri.begin(), pri.end(), n) - pri.begin();
    id--;
    long long ans = id - idx + 2;
    printf("%lld\n", ans);
  }
  return 0;
}
