#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
int Nod(int a, int b) {
  if (a > b) a ^= b ^= a ^= b;
  return !a ? b : Nod(b % a, a);
}
bool erath[1000100];
bool square[1000100];
int ans[1000100];
void Solve() {
  int i, j, k, n, m;
  for (i = 2; i < 1000100; i++) {
    if (!erath[i]) {
      for (j = i + i; j < 1000100; j += i) erath[j] = true;
      long long a = ((long long)i) * i;
      if (a < 1000100) square[a] = true;
    }
  }
  ans[1] = 1;
  for (i = 2; i < 1000100; i++) {
    ans[i] = ans[i - 1];
    if (!erath[i])
      ans[i]++;
    else if (square[i])
      ans[i]--;
  }
  int t;
  scanf("%d", &(t));
  while (t--) {
    scanf("%d", &(i));
    printf("%d\n", ans[i]);
  }
}
int main() {
  Solve();
  return 0;
}
