description: 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
solution: #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';
    }
  }
  