#include <bits/stdc++.h>
using namespace std;
ofstream g("date.out");
const int n = 1000000;
bool prim[n + 5];
int primes[1000005], cntprimes = 0, cate[1000005], sqr[1000005];
int gcd(int a, int b) {
  int r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 2; i <= n; ++i) {
    if (prim[i] == 0) {
      primes[++cntprimes] = i;
      for (int j = i * 2; j <= n; j += i) {
        prim[j] = 1;
      }
      cate[i]++;
    }
  }
  for (int i = 1; i <= 1000; i++) {
    sqr[i * i] = i;
  }
  for (int i = 1; i <= n; i++) {
    sqr[i] = max(sqr[i], sqr[i - 1]);
  }
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += cate[i];
    cate[i] = sum;
  }
  for (int i = 1; i <= t; i++) {
    int x;
    cin >> x;
    int p = sqr[x];
    cout << cate[x] - cate[p] + 1 << '\n';
  }
}
