#include <bits/stdc++.h>
using namespace std;
int f[1000050], t[1000050], x, k, kq[1000050];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (long long i = 2; i <= 1e6; i++)
    if (f[i] == 0) {
      for (long long j = i * i; j <= 1e6; j += i) f[j] = 1;
      t[i] = t[i - 1] + 1;
    } else
      t[i] = t[i - 1];
  cin >> x;
  while (x--) {
    cin >> k;
    if (kq[k] != 0)
      cout << kq[k] << '\n';
    else {
      int z = sqrt(k);
      kq[k] = t[k] - t[z] + 1;
      cout << kq[k] << '\n';
    }
  }
}
