#include <bits/stdc++.h>
const int INF = 1000000001;
using namespace std;
vector<bool> ara(1000180, true);
long long p[1000180];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long t;
  cin >> t;
  int i, j, root;
  root = sqrt(1000179);
  for (i = 2; i <= root; i++) {
    if (ara[i] == 1) {
      for (j = 2; i * j <= 1000179; j++) {
        if (ara[i * j] == 0) continue;
        ara[i * j] = 0;
      }
    }
  }
  p[1] = 1;
  for (long long k = 2; k < 1000179; k++) {
    p[k] = p[k - 1] + ara[k];
    double m = sqrt(k);
    if (m == (long long)m) {
      if (ara[(long long)m] == 1) p[k]--;
    }
  }
  while (t--) {
    long long n, k, i, x, w, c;
    cin >> n;
    if (n == 1 || n == 2 || n == 3) {
      cout << n << '\n';
      continue;
    }
    cout << p[n] << '\n';
  }
  return 0;
}
