#include <bits/stdc++.h>
const long long INF = 1000000001;
using namespace std;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long n;
  cin >> n;
  long long C = 1000179;
  vector<long long> d(C);
  vector<bool> prime(C, true);
  prime[0] = prime[1] = false, d[0] = 0;
  for (long long q = 2; q < C; q++) {
    if (prime[q]) {
      for (long long q1 = q * q; q1 < C; q1 += q) {
        prime[q1] = false;
      }
    }
  }
  for (long long q = 1; q < C; q++) {
    d[q] = d[q - 1] + prime[q];
    if ((long long)sqrt(q) * (long long)sqrt(q) == q) {
      d[q] -= prime[(long long)sqrt(q)];
    }
  }
  for (long long q = 0; q < n; q++) {
    long long k;
    cin >> k;
    cout << d[k] + 1 << '\n';
  }
  return 0;
}
