#include <bits/stdc++.h>
using namespace std;
bool prime[1000005];
int_fast64_t dp[1000005];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int_fast64_t i = 2; i <= 1000000; ++i)
    if (!prime[i])
      for (int_fast64_t j = i * i; j <= 1000000; j += i) prime[j] = 1;
  dp[1] = 1;
  for (int_fast64_t i = 2; i <= 1000000; ++i) {
    dp[i] += dp[i - 1];
    if (!prime[i]) ++dp[i];
    if (sqrt(i) == (int_fast64_t)(sqrt(i)) && !prime[(int_fast64_t)sqrt(i)])
      --dp[i];
  }
  int_fast64_t t;
  cin >> t;
  while (t--) {
    int_fast64_t n;
    cin >> n;
    cout << dp[n] << '\n';
  }
}
