#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long erat[1000042] = {0};
vector<long long> primes;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  primes.push_back(1);
  for (long long i = 2; i < 1000042; i++)
    if (!erat[i]) {
      primes.push_back(i);
      erat[i] = i;
      for (long long j = i * i; j < 1000042; j += i) erat[j] = i;
    }
  long long t = 0;
  cin >> t;
  while (t--) {
    long long n = 0;
    cin >> n;
    long long l1 = 0, r1 = primes.size(), l2 = 0, r2 = primes.size();
    long long ans1 = 0, ans2 = 0;
    while (r1 - l1 > 1) {
      long long m1 = ((l1 + r1) >> 1);
      if (primes[m1] <= n)
        l1 = m1;
      else
        r1 = m1;
    }
    ans1 = r1;
    if (primes[ans1] > n) ans1 = l1;
    while (r2 - l2 > 1) {
      long long m2 = ((l2 + r2) >> 1);
      if (primes[m2] * primes[m2] <= n)
        l2 = m2;
      else
        r2 = m2;
    }
    ans2 = r2;
    if (primes[ans2] * primes[ans2] > n) ans2 = l2;
    printf("%d\n", ans1 - ans2 + 1);
  }
  return 0;
}
