#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  int t;
  vector<long long> primes;
  vector<long long> sqprimes;
  const long long N = 1e6;
  for (long long i = 2; i <= N; i++) {
    if (isPrime(i)) primes.push_back(i);
    if (isPrime(i)) sqprimes.push_back(i * i);
  }
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long ans = 1;
    long long l = 0, r = (int)primes.size() - 1;
    long long idx = 0;
    long long idxPrime = 0;
    long long idxSqPrime = 0;
    while (l <= r) {
      long long mid = l + (r - l) / 2;
      if (primes[mid] > n) {
        r = mid - 1;
      } else {
        l = mid + 1;
        idxPrime = mid + 1;
      }
    }
    l = 0, r = (int)sqprimes.size() - 1;
    while (l <= r) {
      long long mid = l + (r - l) / 2;
      if (sqprimes[mid] > n) {
        r = mid - 1;
      } else {
        l = mid + 1;
        idxSqPrime = mid + 1;
      }
    }
    cout << idxPrime - idxSqPrime + 1 << "\n";
  }
}
