#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
vector<int> primes;
bitset<MAXN> done;
void criba() {
  done[1] = true;
  for (int i = 4; i < MAXN; i += 2) done[i] = true;
  for (int i = 3; i * i <= MAXN; i += 2)
    if (!done[i])
      for (int j = i + i; j < MAXN; j += i) done[j] = true;
  for (int i = int(1); i < int(MAXN); i++)
    if (!done[i]) primes.push_back(i);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ;
  criba();
  int t;
  cin >> t;
  for (int i = 0; i < int(t); i++) {
    int x;
    cin >> x;
    int ind = upper_bound((primes).begin(), (primes).end(), int(sqrt(x))) -
              primes.begin() - 1;
    int r =
        upper_bound((primes).begin(), (primes).end(), x) - primes.begin() - 1;
    cout << r - ind + 1 << '\n';
  }
  return 0;
}
