#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
};
template <typename T>
void view(T e) {
  cout << e << endl;
}
void view(vector<string>& v) {
  cout << endl;
  for (auto& s : v) {
    view(s);
  }
  cout << endl;
}
template <typename T>
void view(vector<T>& v) {
  for (auto& e : v) {
    cout << e << " ";
  }
  cout << endl;
}
template <typename T>
void view(vector<vector<T>>& vv) {
  cout << endl;
  for (auto& v : vv) {
    view(v);
  }
}
template <typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
void start() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
}
void solve() {
  long long n;
  cin >> n;
  set<long long> st;
  for (long long i = 1; i * i <= n; i++) {
    if (i * i * i <= n) {
      st.insert(i * i * i);
    }
    st.insert(i * i);
  }
  cout << (long long)st.size() << "\n";
}
int32_t main() {
  start();
  long long t;
  cin >> t;
  while (t--) solve();
}

### Prompt

Create a solution in Cpp for the following problem:

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;
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
};
template <typename T>
void view(T e) {
  cout << e << endl;
}
void view(vector<string>& v) {
  cout << endl;
  for (auto& s : v) {
    view(s);
  }
  cout << endl;
}
template <typename T>
void view(vector<T>& v) {
  for (auto& e : v) {
    cout << e << " ";
  }
  cout << endl;
}
template <typename T>
void view(vector<vector<T>>& vv) {
  cout << endl;
  for (auto& v : vv) {
    view(v);
  }
}
template <typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
void start() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
}
void solve() {
  long long n;
  cin >> n;
  set<long long> st;
  for (long long i = 1; i * i <= n; i++) {
    if (i * i * i <= n) {
      st.insert(i * i * i);
    }
    st.insert(i * i);
  }
  cout << (long long)st.size() << "\n";
}
int32_t main() {
  start();
  long long t;
  cin >> t;
  while (t--) solve();
}

```