#include <bits/stdc++.h>
using namespace std;
vector<int> v;
const double eps = 0.000001;
long long i0, n;
bool ispr(int num) {
  if (num == 1) return 0;
  if (num == 2 || num == 3) return 1;
  if (num % 6 != 1 && num % 6 != 5) return 0;
  int tmp = sqrt(num);
  for (int i = 5; i <= tmp; i += 6)
    if (num % i == 0 || num % (i + 2) == 0) return 0;
  return 1;
}
long long dfs(int p, int num, int k, int r) {
  long long cnt = 0, tmp;
  if (k == 0) {
    tmp = (long long)(pow(n, 1.0 / num) + eps);
    if ((long long)(pow(tmp, num) + eps) > n)
      tmp -= 2;
    else
      tmp--;
    cnt += tmp > 0 ? tmp * ((r % 2) ? 1 : -1) : 0;
  }
  if (k && p < 17) {
    if (num * v[p] < 60) cnt += dfs(p + 1, num * v[p], k - 1, r);
    cnt += dfs(p + 1, num, k, r);
  }
  return cnt;
}
int main() {
  for (int i = 2; i <= 100; i++)
    if (ispr(i)) v.push_back(i);
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld", &n);
    printf("%lld\n",
           n - 1 - dfs(0, 1, 1, 1) - dfs(0, 1, 2, 2) - dfs(0, 1, 3, 3));
  }
  return 0;
}
