#include <bits/stdc++.h>
using namespace std;
long long s[1000005];
long long s1[1000005];
int solve() {
  long long i, j;
  memset(s, 0, sizeof(s));
  memset(s1, 0, sizeof(s1));
  long long p = 2;
  while (p * p < 1000005) {
    if (s[p] == 0) {
      for (i = p * p; i < 1000005; i += p) {
        if (s[i] == 0) {
          s[i] = 1;
        }
      }
    }
    p += 1;
  }
  for (i = 2; i < 1000005; i++) {
    if (s[i] == 0) s1[i] = 1;
    s1[i] += s1[i - 1];
  }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
  long long t;
  cin >> t;
  long long i, j, n, x;
  for (i = 0; i < t; i++) {
    long long ans = 0;
    cin >> n;
    j = sqrt(n);
    x = s1[n] - s1[j];
    cout << x + 1 << "\n";
  }
  return 0;
}
