#include <bits/stdc++.h>
using namespace std;
void testcase(long long t) { cout << "Case #" << t << ": "; }
void online() {}
const long long mod = 1e9 + 7;
long long n, N;
vector<long long> prime, prefix;
void getSeive() {
  prefix[1] = 1;
  for (long long i = 2; i < N; i++) {
    if (prime[i]) {
      prefix[i] = prefix[i - 1];
    } else {
      prefix[i] = prefix[i - 1] + 1;
      for (long long j = i * i; j < N; j += i) prime[j] = 1;
    }
  }
}
long long solve(long long n) {
  long long x = sqrt(n);
  long long ans = prefix[n] - prefix[x] + 1;
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  long long T = 1;
  cin >> T;
  N = 1e6 + 1;
  prime.resize(N, 0);
  prefix.resize(N);
  getSeive();
  for (long long t = 1; t <= T; t++) {
    cin >> n;
    if (n < 4)
      cout << n << "\n";
    else
      cout << solve(n) << "\n";
  }
  return 0;
}
