#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6 + 5, inf = 1e18;
long long prime[N + 1];
long long cntPrimes[N + 1];
void pre() {
  fill(prime + 2, prime + N, true);
  for (long long i = 2; i <= N; i++)
    if (prime[i]) {
      for (long long j = 2 * i; j <= N; j += i) {
        prime[j] = false;
      }
    }
  long long cnt = 0;
  for (long long i = 0; i <= N; i++) {
    cnt += prime[i];
    cntPrimes[i] = cnt;
  }
}
long long Pi(long long n) { return cntPrimes[n]; }
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  pre();
  long long T;
  cin >> T;
  while (T--) {
    long long n;
    cin >> n;
    long long root = sqrt(n);
    long long ans = Pi(n) - Pi(root) + 1;
    cout << ans << '\n';
  }
}
