#include <bits/stdc++.h>
using namespace std;
long long a[1000009 + 10], p[1000009 + 10];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long i = 2, j;
  while (i <= 1000009) {
    p[i] = p[i - 1];
    if (a[i] == 0) {
      p[i]++;
      j = i + i;
      while (j <= 1000009) {
        a[j] = i;
        j += i;
      }
    }
    i++;
  }
  cin >> i;
  long long x;
  while (i--) {
    cin >> j;
    x = p[j] + 1;
    j = sqrt(j);
    x -= p[j];
    cout << x << "\n";
  }
}
