#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using lld = long double;
template <typename t>
inline void print(const t& v) {
  for (const auto& i : v) {
    std::cout << i << " ";
  }
  std::cout << '\n';
}
template <typename t>
inline void printt(const t& v) {
  for (const auto& i : v) {
    std::cout << i.first << " " << i.second << '\n';
  }
  std::cout << '\n';
}
template <typename INT>
INT gcd(INT a, INT b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <typename INT>
std::map<INT, int> factorize(INT n) {
  map<INT, int> make_pair;
  for (INT i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      n /= i;
      make_pair[i]++;
    }
  }
  if (n > 1) make_pair[n] += 1;
  return make_pair;
}
ll bin_pow(ll a, ll b) {
  if (b == 0) return 1;
  long long res = bin_pow(a, b / 2);
  if (b % 2)
    return res * res * a;
  else
    return res * res;
}
int digit(ll i) { return i > 0 ? (int)log10((double)i) + 1 : 1; }
vector<bool> isPrime(2000000, true);
vector<int> prefixPrime;
void make_seive() {
  isPrime[0] = false;
  isPrime[1] = false;
  for (int i = 2; i <= sqrt(2000000); i++) {
    if (isPrime[i]) {
      for (int j = i * 2; j <= 2000000; j += i) {
        isPrime[j] = false;
      }
    }
  }
}
void solve() {
  int n;
  cin >> n;
  cout << prefixPrime[n] - prefixPrime[floor(sqrt(n))] + 1 << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  make_seive();
  prefixPrime.push_back(0);
  prefixPrime.push_back(0);
  for (int i = 2; i < 2000000; i++) {
    if (isPrime[i])
      prefixPrime.push_back(prefixPrime.back() + 1);
    else
      prefixPrime.push_back(prefixPrime.back());
  }
  int t = 1;
  cin >> t;
  while (t--) solve();
}
