#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
  os << '(' << a.first << ',' << a.second << ')';
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
  for (auto x : v) os << x << ' ';
  return os;
}
void debug() { cerr << '\n'; }
template <typename H, typename... T>
void debug(H a, T... b) {
  cerr << a;
  if (sizeof...(b)) cerr << ", ";
  debug(b...);
}
vector<bool> get_prime(int n) {
  vector<bool> prime(n + 1, true);
  if (n >= 0) prime[0] = false;
  if (n >= 1) prime[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (prime[i]) {
      for (int j = i + i; j <= n; j += i) prime[j] = false;
    }
  }
  return (prime);
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  auto p = get_prime(2000000);
  vector<ll> d;
  for (int i = 0; i < (int)(1000000); ++i)
    if (p[i]) d.push_back(i);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    ll a = sqrt(n);
    int ans2 = 1;
    ans2 +=
        upper_bound(d.begin(), d.end(), n) - lower_bound(d.begin(), d.end(), a);
    if (p[a]) ans2--;
    cout << ans2 << "\n";
  }
}
