#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
const int MAXN = 1e6 + 10;
int lp[MAXN];
long long d[MAXN];
void solve() {
  long long n;
  cin >> n;
  long long sq = sqrt(n);
  cout << d[n] - d[sq] + 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i < MAXN; i += 2) lp[i] = 2;
  for (long long i = 3; i * i < MAXN; i += 2) {
    if (!lp[i]) {
      lp[i] = i;
      for (long long j = i * i; j < MAXN; j += (i + i))
        if (!lp[j]) lp[j] = i;
    }
  }
  for (int i = 2; i < MAXN; ++i)
    if (!lp[i]) lp[i] = i;
  for (int i = 2; i < MAXN; ++i) d[i] = d[i - 1] + (lp[i] == i);
  int T = 1;
  cin >> T;
  while (T--) solve(), cout << '\n';
  return 0;
}
