#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int N = 1000001;
void setIO(string name = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if ((int)(name).size()) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
}
bool isPrime(int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
int main() {
  setIO();
  vector<int> Ans(1000001, 0);
  vector<int> arr(1000001, 0);
  for (long long i = 2; i < 1000001; i++) {
    if (isPrime(i)) {
      arr[i]++;
      if (i < sqrt(1000001)) arr[i * i]--;
    }
  }
  for (int i = 0; i < (1000001); i++) {
    if (i) Ans[i] += Ans[i - 1];
    Ans[i] += arr[i];
  }
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    cout << Ans[n] + 1 << "\n";
  }
}
