#include <bits/stdc++.h>
using namespace std;
const double kEps(1e-8);
#pragma gcc optimize(2)
int gcd(int x, int y) {
  while (y ^= x ^= y ^= x %= y)
    ;
  return x;
}
void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
int qpow(int m, int n) {
  int res = 1;
  while (n) {
    if (n & 1) {
      res *= m;
    }
    n >>= 1;
    m *= m;
  }
  return res;
}
int max(int a, int b) {
  if (a > b) {
    return a;
  } else
    return b;
}
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
signed main() {
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long ans = 1;
    map<long long, long long> mp;
    for (long long i = 2; i < n; ++i) {
      if (i * i > n) {
        break;
      } else {
        if (i * i <= n) {
          ans++;
        }
        if (i * i * i <= n) {
          ans++;
        }
        mp[i * i]++;
        mp[i * i * i]++;
      }
    }
    long long temp = 0;
    for (auto it : mp) {
      if (it.second > 1) {
        temp++;
      }
    }
    mp.clear();
    cout << ans - temp << '\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;
const double kEps(1e-8);
#pragma gcc optimize(2)
int gcd(int x, int y) {
  while (y ^= x ^= y ^= x %= y)
    ;
  return x;
}
void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
int qpow(int m, int n) {
  int res = 1;
  while (n) {
    if (n & 1) {
      res *= m;
    }
    n >>= 1;
    m *= m;
  }
  return res;
}
int max(int a, int b) {
  if (a > b) {
    return a;
  } else
    return b;
}
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
signed main() {
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long ans = 1;
    map<long long, long long> mp;
    for (long long i = 2; i < n; ++i) {
      if (i * i > n) {
        break;
      } else {
        if (i * i <= n) {
          ans++;
        }
        if (i * i * i <= n) {
          ans++;
        }
        mp[i * i]++;
        mp[i * i * i]++;
      }
    }
    long long temp = 0;
    for (auto it : mp) {
      if (it.second > 1) {
        temp++;
      }
    }
    mp.clear();
    cout << ans - temp << '\n';
  }
}

```