Consider some positive integer x. Its prime factorization will be of form x = 2^{k_1} ⋅ 3^{k_2} ⋅ 5^{k_3} ⋅ ...

Let's call x elegant if the greatest common divisor of the sequence k_1, k_2, ... is equal to 1. For example, numbers 5 = 5^1, 12 = 2^2 ⋅ 3, 72 = 2^3 ⋅ 3^2 are elegant and numbers 8 = 2^3 (GCD = 3), 2500 = 2^2 ⋅ 5^4 (GCD = 2) are not.

Count the number of elegant integers from 2 to n.

Each testcase contains several values of n, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^5) — the number of values of n in the testcase.

Each of the next T lines contains a single integer n_i (2 ≤ n_i ≤ 10^{18}).

Output

Print T lines — the i-th line should contain the number of elegant numbers from 2 to n_i.

Example

Input

4
4
2
72
10


Output

2
1
61
6

Note

Here is the list of non-elegant numbers up to 10:

  * 4 = 2^2, GCD = 2; 
  * 8 = 2^3, GCD = 3; 
  * 9 = 3^2, GCD = 2. 



The rest have GCD = 1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
using tp = tuple<ll, ll, ll>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
using ld = long double;
static const ld pi = 3.141592653589793L;
using Array = vector<ll>;
using Matrix = vector<Array>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
struct Edge {
  ll to, cap, rev;
  Edge(ll _to, ll _cap, ll _rev) {
    to = _to;
    cap = _cap;
    rev = _rev;
  }
};
void add_edge(vector<vector<Edge>> &G, ll from, ll to, ll cap, bool revFlag,
              ll revCap) {
  G[from].push_back(Edge(to, cap, (ll)G[to].size()));
  if (revFlag) G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}
vvec<ll> ps(61);
ll nums[61];
ll n;
ll dp[61];
ll pow2[61];
ll nump;
vvec<ll> powp(61);
void factoring(ll n, vec<ll> &ret, bool &flag) {
  flag = false;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) ret.push_back(i);
    int con = 0;
    while (n % i == 0) {
      n /= i;
      con++;
    }
    if (con >= 2) return;
  }
  flag = true;
  if (n != 1) ret.push_back(n);
}
ll pow_2(ll x, ll n2, ll ma) {
  ll ans = 1ll;
  bool flag = true;
  bool flag2 = false;
  while (n2 > 0) {
    if ((n2 & 1) == 1) {
      if (ans > ma / x or flag2) return ma + 1;
      ans = ans * x;
    }
    if (x > ma / x)
      flag2 = true;
    else
      x = x * x;
    n2 >>= 1;
  }
  return ans;
}
void init() {
  nump = 0;
  for (ll i = (ll)(2); i < (ll)(60); ++i) {
    bool flag;
    factoring(i, ps[i], flag);
    if (flag) nums[nump++] = i;
  }
  pow2[0] = 1;
  for (ll i = (ll)(0); i < (ll)(60); ++i) pow2[i + 1] = pow2[i] * 2;
  for (ll i = (ll)(1); i < (ll)(nump); ++i) {
    ll x = nums[i];
    ll mp = 1000001;
    ll ma = 1e18;
    for (ll j = (ll)(2); j < (ll)(mp); ++j) {
      ll ret = pow_2(j, x, ma);
      if (ret > ma) break;
      powp[x].push_back(ret);
    }
  }
}
ll search(ll i) {
  if (dp[i] != -1) return dp[i];
  if (i == 2) {
    ll l = 2;
    ll r = n;
    while (l + 1 < r) {
      ll m = l + r >> 1;
      if (pow_2(m, i, n) == n + 1)
        r = m;
      else
        l = m;
    }
    return dp[i] = l - 1;
  } else {
    return dp[i] = upper_bound((powp[i]).begin(), (powp[i]).end(), n) -
                   powp[i].begin();
  }
}
void solve() {
  cin >> n;
  fill(dp, dp + 61, -1);
  ll ans = n - 1;
  for (ll j = (ll)(0); j < (ll)(nump); ++j) {
    ll i = nums[j];
    if (pow2[i] > n) break;
    ll t = (ps[i].size() % 2) ? -1 : 1;
    ans += t * search(i);
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  init();
  ll t;
  cin >> t;
  for (ll i = (ll)(0); i < (ll)(t - 1); ++i) {
    solve();
  }
  solve();
  return 0;
}
