#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAX = 1e6 + 10;
const ll inf = 1e9;
ll p[MAX], ac[MAX], s[MAX];
int main() {
  for (ll i = 2; i < MAX; i++)
    if (p[i] == 0)
      for (ll j = i; j < MAX; j += i) p[j] = i;
  ll c = 1;
  for (ll i = 1; i < MAX; i++) {
    ac[i] = ac[i - 1] + (p[i] == i ? 1 : 0);
    if ((c + 1) * (c + 1) <= i) c++;
    s[i] = c;
  }
  ll tc, n;
  scanf("%d", &tc);
  while (tc--) {
    scanf("%d", &n);
    printf("%d\n", ac[n] - ac[s[n]] + 1);
  }
}
