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: import java.io.*;
  import java.util.*;
  
  public class B {
      public static void main(String[] args) {
          Pre.compute();
          for (int t = IO.getInt(), i = 0; i < t; i++)
              new SolB().solve();
          IO.close();
      }
  }
  
  class SolB {
  
      int n;
  
      SolB() {
          n = IO.getInt();
      }
  
      void solve() {
          IO.writer.println(bins(Pre.nums, n)+1);
      }
  
      int bins(int[] nums, int v) {
          int l = 0, r = nums.length-1;
          while (l < r) {
              if (l == r-1) {
                  if (v >= nums[r])
                      l = r;
                  else
                      r = l;
                  continue;
              }
              int mid = (l + r) / 2;
              if (nums[mid] > v)
                  r = mid;
              else
                  l = mid;
          }
          return l;
      }
  }
  
  class Pre {
      static int[] nums;
  
      static void compute() {
          
          Set<Integer> set = new TreeSet<>();
          for (int i = 1; i < Math.sqrt(Constants.MAX_N)+1; i++)
              set.add(i*i);
          for (int i = 2; i < 1001; i++)
              set.add(i*i*i);
          List<Integer> list = new ArrayList<>(set);
          nums = new int[list.size()];
          for (int i = 0; i < list.size(); i++)
              nums[i] = list.get(i);
      }
  }
  
  class Constants {
      public static final int MAX_N = 1000000009;
  }
  
  class IO {
      public static final PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
      
      private static byte[] bytes = new byte[1<<15];
      private static int i, n;
   
      private static StringTokenizer tokens;
   
      private static byte getByte() {
          if (i == n) {
              i = 0;
              n = 0;
              try {
                  n = System.in.read(bytes);
              } catch (IOException e) {}
          }
          return i < n ? bytes[i++] : 0;
      }
   
      private static byte skip() {
          byte c = getByte();
          while (c <= ' ')
              c = getByte();
          return c;
      }
   
      public static int getInt() {
          int a = 0;
          for (byte c = skip(); c > ' '; c = getByte())
              a = a * 10 + (c - '0');
          return a;
      }
   
      public static long getLong() {
          long a = 0l;
          for (byte c = skip(); c > ' '; c = getByte())
              a = a * 10 + (c - '0');
          return a;
      }
   
      public static String readLine() {
          StringBuilder sb = new StringBuilder();
          for (byte c = getByte(); c >= ' '; c = getByte())
              sb.append((char) c);
          return sb.toString();
      }
   
      private static void initializeTokens() {
          while (null == tokens || !tokens.hasMoreTokens())
              tokens = new StringTokenizer(readLine());
      }
   
      public static String next() {
          initializeTokens();
          return tokens.nextToken();
      }
   
      public static String next(String delim) {
          initializeTokens();
          return tokens.nextToken(delim);
      }
   
      public static int nextInt() {
          return Integer.parseInt(next());
      }
   
      public static long nextLong() {
          return Long.parseLong(next());
      }
   
      public static void close() {
          writer.close();
      }
  }