#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 5;
long long t, cnt;
long long n, k;
long long pri[MAX];
long long num[MAX];
long long ans;
int main() {
  for (long long i = 2; i < MAX; ++i) {
    if (!pri[i]) pri[++pri[0]] = i;
    for (long long j = 1; j <= pri[0] && pri[j] <= MAX / i; ++j) {
      pri[pri[j] * i] = 1;
      if (i % pri[j] == 0) break;
    }
  }
  cnt = 0;
  long long pos = 1;
  for (long long i = 2; i < MAX; ++i) {
    if (i >= pri[pos]) {
      pos++;
      cnt++;
    }
    num[i] = cnt;
  }
  cin >> t;
  while (t--) {
    scanf("%lld", &n);
    long long sqrtt = sqrt(n);
    ans = num[n] - (num[sqrtt] - 1);
    printf("%lld\n", ans);
  }
  return 0;
}
