#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long inf = -1;
const long long sz = 1e6 + 10;
const long long m = 1e6 + 10;
vector<long long> prime;
bool sieve[m + 2];
void primeSieve() {
  memset(sieve, true, sizeof(sieve));
  sieve[0] = sieve[1] = false;
  prime.push_back(2);
  for (long long i = 4; i <= m; i += 2) sieve[i] = false;
  long long sqrtn = sqrt(m);
  for (long long i = 3; i <= sqrtn; i += 2) {
    if (sieve[i]) {
      for (long long j = i * i; j <= m; j += 2 * i) sieve[j] = false;
    }
  }
  for (long long i = 3; i <= m; i += 2)
    if (sieve[i]) prime.push_back(i);
}
long long ar[sz];
void pre() {
  for (long long i = 0; i < (long long)prime.size(); i++) {
    ar[i] = prime[i] * prime[i];
  }
}
signed main() {
  primeSieve();
  pre();
  long long len = prime.size();
  long long n;
  long long x;
  scanf("%lld", &n);
  for (long long i = 0; i < n; i++) {
    scanf("%lld", &x);
    long long pos = upper_bound(prime.begin(), prime.end(), x) - prime.begin();
    long long ex = upper_bound(ar, ar + len, x) - ar;
    printf("%lld\n", pos - ex + 1);
  }
}
