#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
bool ispoweroftwo(long long n) { return n & (!(n & (n - 1))); }
long long mod = 1000000007;
long long dx[] = {1, 0, -1, 0};
long long dy[] = {0, -1, 0, 1};
bool test = 1;
const long long inf = 1e9;
const long long N = 1e6 + 5;
bool OK[N];
vector<long long> primes;
void sieve() {
  for (long long i = 2; i < N; ++i) OK[i] = true;
  for (long long i = 2; i < N; ++i)
    if (OK[i]) {
      primes.push_back(i);
      for (long long j = i + i; j < N; j += i) OK[j] = false;
    }
}
long long k, n;
void solve(long long tc = 0) {
  cin >> n;
  long long x = sqrt(n);
  long long r = upper_bound(primes.begin(), primes.end(), n) - primes.begin();
  long long l = upper_bound(primes.begin(), primes.end(), x) - primes.begin();
  cout << (r - l + 1) << "\n";
}
signed main() {
  sieve();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t = 1;
  if (test) cin >> t;
  for (long long i = 1; i <= t; ++i) {
    solve(i);
  }
  return 0;
}
