#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const long long mod = 1000 * 1000 * 1000 + 7;
const long long inf = 1ll * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 7;
const long long mod2 = 998244353;
const long long N = 1000 * 1000 + 100;
const long double pi = 3.141592653589793;
long long power(long long x, long long y, long long p = LLONG_MAX) {
  long long res = 1;
  x %= p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long lp[N];
long long p[N];
long long ans[N];
vector<long long> prime;
void sieve() {
  bool a[N] = {0};
  for (long long i = 2; i < N; i++) {
    if (!a[i]) {
      p[i] = 1;
      prime.push_back(i);
      for (long long j = (i * i); j < N; j += i) {
        a[j] = 1;
      }
    }
  }
}
void solve() {
  for (long long i = 2; i < N; i++) {
    if (p[i] == 1) {
      lp[i] = i;
      for (long long j = (i * i); j < N; j += i) {
        lp[j] = min(lp[j], i);
      }
    }
  }
}
void solve2() {
  ans[0] = 0;
  ans[1] = 0;
  for (long long i = 2; i < N; i++) {
    ans[i] = ans[i - 1];
    if (lp[i] == i) {
      ans[i]++;
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  sieve();
  solve();
  solve2();
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long j = sqrt(n);
    cout << (ans[n] - ans[j] + 1) << "\n";
  }
  return 0;
}
