#include <bits/stdc++.h>
using namespace std;
void dout() { cerr << endl; }
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
  cerr << H << ' ';
  dout(T...);
}
using ll = long long;
using pii = pair<ll, ll>;
using ld = double;
using pll = pair<long long, long long>;
template <typename T>
void do_uniq(vector<T> vec) {
  sort((vec).begin(), (vec).end());
  vec.resize(unique((vec).begin(), (vec).end()) - vec.begin());
}
ll mod = 998244353;
ll add(ll a, ll b) { return (a + b) % mod; }
ll ml(ll a, ll b) { return ((a * 1ll) * b) % mod; }
ll sub(ll a, ll b) { return add(a, mod - b); }
ll sq(ll v) { return ml(v, v); }
ll b_p(ll b, ll p) {
  if (p == 0) return 1;
  if (p & 1) return ml(b, b_p(b, p ^ 1));
  return sq(b_p(b, p >> 1));
}
const int MAXN = 2e6 + 112;
bool is_primes[MAXN];
int precs[MAXN];
void prec() {
  for (int i = 2; i < MAXN; ++i) is_primes[i] = true;
  for (int i = 2; i < MAXN; ++i) {
    precs[i] += precs[i - 1];
    if (!is_primes[i]) {
      precs[i]++;
      continue;
    }
    if ((i * 1ll) * i < MAXN) {
      precs[i * i]++;
    }
    for (int j = 2 * i; j < MAXN; j += i) {
      is_primes[j] = false;
    }
  }
}
void solve() {
  prec();
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    cout << n - precs[n] << "\n";
  }
}
void multisolve() {
  int t;
  cin >> t;
  int i = 1;
  while (t--) {
    solve();
    i++;
  }
}
void gen() {
  int n = 240;
  cout << n << "\n";
  for (int i = 0; i < n; ++i) {
    cout << rand() << "\n";
  }
  cout << 1 << "\n";
  cout << rand();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(20);
  solve();
}
