#include <bits/stdc++.h>
using namespace std;
long long int seive[1000005];
long long int pref[1000005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (long long int i = 0; i < 1000005; i++) {
    seive[i] = 1;
  }
  seive[0] = 0;
  for (long long int i = 2; i < 1000005; i++) {
    for (long long int j = i * i; j < 1000005; j += i) {
      seive[j] = 0;
    }
  }
  memset(pref, 0, sizeof(pref));
  pref[1] = 1;
  for (long long int i = 2; i < 1000005; i++) {
    pref[i] = pref[i - 1] + seive[i];
  }
  long long int t;
  cin >> t;
  while (t--) {
    long long int n;
    cin >> n;
    long long int z = sqrt(n);
    if ((z + 1) * (z + 1) <= n) {
      z++;
    }
    cout << pref[n] - pref[z] + 1 << "\n";
  }
}
