#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> primes({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
                   59});
vector<pair<ll, ll>> powers;
vector<ll> seq[60];
bool use[60];
void GenPowers() {
  for (int mask = 1; mask < (1 << primes.size()); mask++) {
    ll value = 1;
    for (int i = 0; i < primes.size(); i++) {
      if (mask & (1 << i)) {
        value *= primes[i];
        if (value > 59) {
          break;
        }
      }
    }
    if (value < 60) {
      if (__builtin_popcount(mask) & 1) {
        powers.push_back({value, 1});
      } else {
        powers.push_back({value, -1});
      }
      use[value] = true;
    }
  }
  sort(powers.begin(), powers.end());
}
bool overflows(ll a, ll b) { return a > numeric_limits<ll>::max() / b; }
void GenSeq() {
  for (ll k = 1; k <= 1000000; k++) {
    ll x = k;
    for (int p = 2; p < 60; p++) {
      if (overflows(k, x)) break;
      x *= k;
      if (x > 1.e18) break;
      if (use[p]) {
        seq[p].push_back(x);
      }
    }
  }
}
ll pot(ll p, ll x) {
  if (p == 0) {
    return 1ll;
  }
  ll mid = pot(p / 2ll, x);
  ll ret = mid * mid;
  if (p % 2) {
    ret *= x;
  }
  return ret;
}
bool check2(ll n, ll p, ll x) { return pot(p, x) <= n; }
bool check(ll n, ll p, ll x) {
  if (p == 2) return x * x <= n;
  if (x > seq[p].size()) return false;
  return seq[p][x - 1] <= n;
}
ll count(ll n, ll p) {
  ll x = floor(exp(log(n) / p));
  if (check(n, p, x)) {
    do {
      x++;
    } while (check(n, p, x));
    return x - 2ll;
  } else {
    do {
      x--;
    } while (not check(n, p, x));
    return x - 1ll;
  }
}
ll query(ll n) {
  ll res = n - 1;
  for (auto p : powers) {
    res -= p.second * count(n, p.first);
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  GenPowers();
  GenSeq();
  int t;
  cin >> t;
  for (int tc = 0; tc < t; tc++) {
    ll n;
    cin >> n;
    cout << query(n) << '\n';
  }
}
