#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
bool lol[maxn];
int cnt[maxn];
vector<long long> p;
void crivo() {
  lol[1] = 1;
  for (long long i = 2; i < maxn; i++) {
    cnt[i] = cnt[i - 1];
    if (lol[i] == 0) {
      p.push_back(i * i);
      for (long long j = i * i; j < maxn; j += i) {
        lol[j] = 1;
      }
    } else
      cnt[i]++;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  crivo();
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    auto it = upper_bound(p.begin(), p.end(), n);
    int qtd = it - p.begin();
    cout << n - qtd - cnt[n] << "\n";
  }
  return 0;
}
