#include <bits/stdc++.h>
using namespace std;
int prime[150000];
int lp[1001002];
int phi[1001002];
class prime_class {
 public:
  long top;
  prime_class() {
    int i, i2, j;
    top = 0;
    lp[0] = 0;
    lp[1] = 1;
    for (i = 2; i < 1001002; i++) lp[i] = 0;
    top = 0;
    for (i = 2; i < 1001002; ++i) {
      if (lp[i] == 0) {
        lp[i] = i;
        prime[top++] = i;
      }
      for (j = 0; (j < top) && (prime[j] <= lp[i]) && (i * prime[j] < 1001002);
           ++j)
        lp[i * prime[j]] = prime[j];
    }
  }
  bool isprime(long long key) {
    if (key < 1001002)
      return (lp[key] == key) && (key >= 2);
    else {
      int i;
      for (i = 0; (i < top) && (prime[i] * prime[i] <= key); i++)
        if (key % prime[i] == 0) return false;
      return true;
    }
  }
  unordered_map<int, int> factorize(int key) {
    unordered_map<int, int> ans;
    while (lp[key] != key) {
      ans[lp[key]]++;
      key /= lp[key];
    }
    if (key > 1) ans[key]++;
    return ans;
  }
  int get_phi(int key) {
    int ans = key, last = 0;
    while (lp[key] != key) {
      if (lp[key] != last) {
        last = lp[key];
        ans -= ans / last;
      }
      key /= lp[key];
    }
    if ((key > 1) && (key != last)) ans -= ans / key;
    return ans;
  }
  void calc_all_phi(int n) {
    int i, j, k;
    for (int i = 1; i < n; i++) phi[i] = i;
    for (int i = 2; i < n; i++) {
      if (phi[i] == i) {
        for (int j = i; j < n; j += i) {
          phi[j] /= i;
          phi[j] *= i - 1;
        }
      }
    }
  }
  vector<pair<long long, long long>> factorize_full(long long key) {
    vector<pair<long long, long long>> ans;
    long i, ct, sq = sqrt(key) + 10;
    for (i = 0; (i < top) && (prime[i] <= sq); i++)
      if (key % prime[i] == 0) {
        ct = 0;
        while (key % prime[i] == 0) {
          ct++;
          key /= prime[i];
        }
        ans.push_back({prime[i], ct});
      }
    if (key > 1) {
      ans.push_back({key, 1});
    }
    return ans;
  }
  void generate_divisors(int step, int v, vector<pair<int, int>>& fp,
                         vector<int>& ans) {
    if (step < fp.size()) {
      generate_divisors(step + 1, v, fp, ans);
      for (int i = 1; i <= fp[step].second; i++) {
        v *= fp[step].first;
        generate_divisors(step + 1, v, fp, ans);
      }
    } else
      ans.push_back(v);
  }
  void generate_divisors_full(long long step, long long v,
                              vector<pair<long long, long long>>& fp,
                              vector<long long>& ans) {
    if (step < fp.size()) {
      generate_divisors_full(step + 1, v, fp, ans);
      for (int i = 1; i <= fp[step].second; i++) {
        v *= fp[step].first;
        generate_divisors_full(step + 1, v, fp, ans);
      }
    } else
      ans.push_back(v);
  }
  vector<int> get_divisors(int key) {
    unordered_map<int, int> f = factorize(key);
    int n = f.size();
    vector<pair<int, int>> fp;
    for (auto p : f) fp.push_back(p);
    vector<int> ans;
    generate_divisors(0, 1, fp, ans);
    return ans;
  }
  vector<long long> get_divisors_full(long long key) {
    vector<pair<long long, long long>> f = factorize_full(key);
    int n = f.size();
    vector<pair<long long, long long>> fp;
    for (auto p : f) fp.push_back(p);
    vector<long long> ans;
    generate_divisors_full(0, 1, fp, ans);
    return ans;
  }
  long long get_divisors_count(long long key) {
    vector<pair<long long, long long>> f = factorize_full(key);
    long long ans = 1;
    for (auto p : f) ans *= (p.second + 1);
    return ans;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  prime_class pr;
  int t, n, i, j, k, ans, sq;
  vector<int> s(1001002, 0);
  for (i = 2; i < 1001002; i++) {
    if (pr.isprime(i))
      s[i] = s[i - 1] + 1;
    else
      s[i] = s[i - 1];
  }
  cin >> t;
  while (t--) {
    cin >> n;
    sq = sqrt(n);
    ans = s[n] - s[sq] + 1;
    cout << ans << "\n";
  }
  return 0;
}
