#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long double PI = acos((long double)-1);
const int maxN = 1e6 + 1;
bool isPrime[maxN];
int cntPrimes[maxN];
vector<int> primes;
void sieve() {
  memset(isPrime, 1, sizeof(isPrime));
  isPrime[0] = isPrime[1] = false;
  for (long long i = 1; i * i < maxN; ++i) {
    if (isPrime[i]) {
      for (long long j = i * i; j < maxN; j += i) {
        isPrime[j] = false;
      }
    }
  }
  for (int i = 2; i < maxN; ++i) {
    cntPrimes[i] += cntPrimes[i - 1];
    if (isPrime[i]) {
      ++cntPrimes[i];
    }
  }
}
void solve() {
  int n;
  cin >> n;
  cout << cntPrimes[n] - cntPrimes[(int)sqrt(n)] + 1 << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  sieve();
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
