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 Solution{
    static PrintWriter out = new PrintWriter(System.out);
    static int mod = 1000000009;
    public static void main(String[] args) throws IOException {
     FastReader fs = new FastReader();	 
    
     int t = fs.nextInt();
     while(t > 0){
      int n = fs.nextInt();
      int sqr = (int) Math.sqrt(n);
      int cub = (int) Math.cbrt(n);
      int both = (int) Math.cbrt(Math.sqrt(n));
      out.println(sqr + cub - both);
      t--;
     }
     out.flush();
   }  
  
    static void op(int[] a, int n){
     int max = Integer.MIN_VALUE;
     for(int i = 0; i < n; i++){
         max = Math.max(max, a[i]);
      }
      for(int i = 0; i < n; i++){
         a[i] = max - a[i];
      }
    }
  
    static int isCs(String x, String y, int n, int m, int[][] dp){
       if(n == 0 || m == 0){
           return 0;
       }
       if(dp[n-1][m-1] != 0) {return dp[n-1][m-1];}
       if(x.charAt(n-1) == y.charAt(m-1)){
          return dp[n-1][m-1] = isCs(x, y, n-1, m-1, dp) + 1;
       }else{
         return dp[n-1][m-1] = Math.max(isCs(x, y, n-1, m, dp), isCs(x, y, n, m-1, dp));
       }  
   }
    
    static int binarySearch(int[] a){
      int n = a.length;
      return 0;
     } 
   
    static boolean distinct(String s){
      for(int i = 0; i < s.length()-1; i++){
        for(int j = i+1; j < s.length(); j++){
           if(s.charAt(i) == s.charAt(j)){
                return false;
            }
        }
      }
      return true;
    }
  
    static long sumOfDigit(long n){
     long sum = 0;
     while(n > 0){
       long rem = n % 10;
       sum += rem;
       n = n / 10;
     }
     return sum;
    }
  
    static void swap(int a, int b){
       int temp = a;
       a = b;
       b = temp;
    }
  
    static int[] numArr(int n){
       int len = countDigit(n);
       int[] a = new int[len];
       int i = 0;
       
       while(i < len){
           a[i] = n % 10;
           n = n / 10;
           i++;          
       }
       return a;
    }  
  
   static void lcs(String X, String Y, int m, int n, int temp)
      {
          int[][] L = new int[m+1][n+1];
     
          // Following steps build L[m+1][n+1] in bottom up fashion. Note
          // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 
          for (int i=0; i<=m; i++)
          {
              for (int j=0; j<=n; j++)
              {
                  if (i == 0 || j == 0)
                      L[i][j] = 0;
                  else if (X.charAt(i-1) == Y.charAt(j-1))
                      L[i][j] = L[i-1][j-1] + 1;
                  else
                      L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
              }
          }
     
          // Following code is used to print LCS
          int index = L[m][n];
          temp = index;
     
          // Create a character array to store the lcs string
          char[] lcs = new char[index+1];
          lcs[index] = '\u0000'; // Set the terminating character
     
          // Start from the right-most-bottom-most corner and
          // one by one store characters in lcs[]
          int i = m;
          int j = n;
          while (i > 0 && j > 0)
          {
              // If current character in X[] and Y are same, then
              // current character is part of LCS
              if (X.charAt(i-1) == Y.charAt(j-1))
              {
                  // Put current character in result
                  lcs[index-1] = X.charAt(i-1); 
                    
                  // reduce values of i, j and index
                  i--; 
                  j--; 
                  index--;     
              }
     
              // If not same, then find the larger of two and
              // go in the direction of larger value
              else if (L[i-1][j] > L[i][j-1])
                  i--;
       else
        j--;
     }
     for(int k=0;k<=temp;k++)
              System.out.print(lcs[k]);
      
      }
  
    static void sortDe(int[] a) {
  		ArrayList<Integer> l = new      ArrayList<>();
  		for (int i : a)
  			l.add(i);
  		Collections.sort(l);
                  int list = l.size() - 1;
  		for (int i = 0; i < a.length; i++)
  		{	a[i] = l.get(list);
                          list--;
                  }
  	}
  
    
    static void bracket(int n){
       for(int i = 0; i < n; i++){
           out.print("(");
       }
       for(int i = 0; i < n; i++){
           out.print(")");
       }
       
    }
  
    static int countDigit(int n){
       return (int) Math.floor(Math.log10(n)) + 1;
    }
  
    static int countDigit(long n){
       return (int) Math.floor(Math.log10(n)) + 1;
    }
  
    static void print(int[] ar){
       for(int i = 0; i < ar.length; i++){
           out.print(ar[i] + " ");
       }
    }
  
    static long countEven(long n){
       long c = 0;
       long rem = 0;
       while(n > 1){
           rem = n % 10;
           if(rem % 2 == 0){
              c++;
           }
           n = n / 10;
       }
       return c;
    }
  
    static boolean divisor(long n){
        int count = 2;
        for(int i = 2; i*i <= n; i++){
             if(n % i == 0){
                 count++;
             }
             if(count < 3){
                  break;
              }
        }
        if(count == 3){return true;}
        else{return false;}      
    }
  
    static String reverseString(String s){
        int j = s.length() - 1;
        String st = new String();
        while(j >= 0){
          st += s.charAt(j);
          j--;
        }
        return st;
     } 
  
    static boolean isPallindrome(String s){
       int i = 0, j = s.length() - 1;
       while(i < j){
          if(s.charAt(i) != s.charAt(j)){
               return false;
           }
           i++;
           j--;
       }
       return true;
    }
  
    static boolean lcsPallindrom(String s){ 
       int i = 0, j = s.length()-1;
       while(i < j){
           if(s.charAt(i) != s.charAt(j)){
               return false;
           }
           i++;
           j--;
       } 
       return true;    
    }
  
    static int[] nprimeNumbers(int n){  
       int[] mark = new int[n+1];
       Arrays.fill(mark, 1);
      
       mark[0] = 0;
       mark[1] = 0;
  
       for(int i = 2; i < mark.length; i++){
           if(mark[i] == 1){
             for(int j = i*i; j < mark.length; j += i){
                  mark[j] = 0;
           }
         }
       }
       return mark;
     }
  
    static long gcd(long a, long b){
      if(b > a){return gcd(b, a);}
      if(b == 0){return a;}     
      return gcd(b, a % b);
    }
  
  
    static int gcd(int a, int b){
      if(b > a){return gcd(b, a);}
      if(b == 0){return a;}     
      return gcd(b, a % b);
    }
  
    static class Pair {
         int lvl;
         int str;
         Pair(int lvl, int str){
            this.lvl = lvl;
            this.str = str;
          }
    }
  
    static class lvlcompare implements Comparator<Pair> {
       public int compare(Pair p1, Pair p2){
          if(p1.lvl == p2.lvl){
                return 0;
           }else if(p1.lvl > p2.lvl){
                return 1;
           }else {
                return -1;
           }
       }
    }  
    
    static long count(long n){
       long ct = 0;
       while(n > 0){
           n = n / 10;
           ct++;
       }
       return ct;
    }
  
    static void sort(int[] a) {
  		ArrayList<Integer> l = new      ArrayList<>();
  		for (int i : a)
  			l.add(i);
  		Collections.sort(l);
  		for (int i = 0; i < a.length; i++)
  			a[i] = l.get(i);
  	}
  
  
    static void sort(long[] a) {
     ArrayList<Long> l = new      ArrayList<>();
      for (long i : a)
       l.add(i);
       Collections.sort(l);
     for (int i = 0; i < a.length; i++) a[i] = l.get(i);
    }
  
  static class FastReader {
  BufferedReader br;
  StringTokenizer st;
   
  public FastReader()
  {br = new BufferedReader(new InputStreamReader(System.in));}
   
  String next()
  { while (st == null || !st.hasMoreElements()) {
  try {st = new StringTokenizer(br.readLine());}
  catch (IOException e) {e.printStackTrace();}}
  return st.nextToken();}
   
  int nextInt() {return Integer.parseInt(next());}
   
  long nextLong() {return Long.parseLong(next());}
   
  double nextDouble(){return Double.parseDouble(next());}
   
  String nextLine()
  { String str = "";
  try {str = br.readLine();}
  catch (IOException e) {e.printStackTrace();}
  return str;
  }
    }
  }