#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ii = pair<int, int>;
using ull = unsigned long long;
using vi = vector<int>;
using vii = vector<ii>;
using llp = pair<ll, ll>;
const ll MAXN = 1e3 + 100, MAXM = 100 + 100, LOG_MAXN = 20, MAXVAL = 2e6 + 100,
         MOD = 1e9 + 7, INF = 1e9 + 7;
template <class A, class B>
ostream &operator<<(ostream &strm, pair<A, B> p) {
  return strm << "{" << p.first << ";" << p.second << "}";
}
template <class A, class B>
ostream &operator<<(ostream &strm, vector<A, B> &v) {
  for (int i = 0; i < v.size(); i++)
    strm << v[i] << ((i + 1 == v.size()) ? "" : " ");
  return strm;
}
bool isLessThanSquare(ll i, ll n) { return i * i <= n; }
bool isLessThanCube(ll i, ll n) { return i * i <= n / i; }
ll bin_search(ll n, bool (*prop)(ll a, ll b)) {
  ll beg = 0, end = n + 1;
  while (end - beg > 1) {
    ll m = ((beg + end) / 2);
    if (prop(m, n))
      beg = m;
    else
      end = m;
  }
  return beg;
}
ll getSixRoot(ll n) {
  ll x = bin_search(n, isLessThanCube);
  return bin_search(x, isLessThanSquare);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ;
  ;
  ;
  int t;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    ll sq = bin_search(n, isLessThanSquare);
    ll cb = bin_search(n, isLessThanCube);
    ll six = getSixRoot(n);
    cout << sq + cb - six << '\n';
  }
}

### Prompt

Construct a cpp code solution to the problem outlined:

Polycarp likes squares and cubes of positive integers. Here is the beginning of the sequence of numbers he likes: 1, 4, 8, 9, ....

For a given number n, count the number of integers from 1 to n that Polycarp likes. In other words, find the number of such x that x is a square of a positive integer number or a cube of a positive integer number (or both a square and a cube simultaneously).

Input

The first line contains an integer t (1 ≤ t ≤ 20) — the number of test cases.

Then t lines contain the test cases, one per line. Each of the lines contains one integer n (1 ≤ n ≤ 10^9).

Output

For each test case, print the answer you are looking for — the number of integers from 1 to n that Polycarp likes.

Example

Input


6
10
1
25
1000000000
999999999
500000000


Output


4
1
6
32591
32590
23125

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ii = pair<int, int>;
using ull = unsigned long long;
using vi = vector<int>;
using vii = vector<ii>;
using llp = pair<ll, ll>;
const ll MAXN = 1e3 + 100, MAXM = 100 + 100, LOG_MAXN = 20, MAXVAL = 2e6 + 100,
         MOD = 1e9 + 7, INF = 1e9 + 7;
template <class A, class B>
ostream &operator<<(ostream &strm, pair<A, B> p) {
  return strm << "{" << p.first << ";" << p.second << "}";
}
template <class A, class B>
ostream &operator<<(ostream &strm, vector<A, B> &v) {
  for (int i = 0; i < v.size(); i++)
    strm << v[i] << ((i + 1 == v.size()) ? "" : " ");
  return strm;
}
bool isLessThanSquare(ll i, ll n) { return i * i <= n; }
bool isLessThanCube(ll i, ll n) { return i * i <= n / i; }
ll bin_search(ll n, bool (*prop)(ll a, ll b)) {
  ll beg = 0, end = n + 1;
  while (end - beg > 1) {
    ll m = ((beg + end) / 2);
    if (prop(m, n))
      beg = m;
    else
      end = m;
  }
  return beg;
}
ll getSixRoot(ll n) {
  ll x = bin_search(n, isLessThanCube);
  return bin_search(x, isLessThanSquare);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ;
  ;
  ;
  int t;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    ll sq = bin_search(n, isLessThanSquare);
    ll cb = bin_search(n, isLessThanCube);
    ll six = getSixRoot(n);
    cout << sq + cb - six << '\n';
  }
}

```