#include <bits/stdc++.h>
int res[1000008];
using namespace std;
int main() {
  bool pr[1000008 + 1];
  memset(pr, true, sizeof(pr));
  int cnt = 0;
  for (int p = 2; p * p <= 1000008; p++) {
    if (pr[p] == true) {
      for (int j = p * p; j <= 1000008; j += p) pr[j] = false;
    }
  }
  for (int i = 2; i <= 1000008; i++) {
    if (pr[i]) {
      cnt++;
    }
    res[i] = cnt;
  }
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int k = sqrt(n);
    int r = res[n] - res[k];
    cout << r + 1 << "\n";
  }
}
