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.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.HashSet;
  import java.util.Random;
  import java.util.Set;
  import java.util.StringTokenizer;
  
  public class CF {
  	public static void main(String[] args) {
  		FastScanner sc = new FastScanner();
  		int t = sc.nextInt();
  		for (int i = 0; i < t; i++) {
  			int n = sc.nextInt();
  			solve(n);
  		}
  	}
  
  	public static void solve(int n) {
  		Set<Long> set = new HashSet<>();
  		set.add(1L);
  		for (long i = 1; i <= Math.cbrt(n); i++) {
  			if ((long) i * i * i <= n) {
  				set.add(i*i*i);
  			}
  		}
  		for (long i = 1; i <= Math.sqrt(n); i++) {
  			if ((long) i * i <= n) {
  				set.add(i*i);
  			}
  		}
  		System.out.println(set.size());
  	}
  
  	private static void shuffleArray(int[] array) {
  		int index;
  		Random random = new Random();
  		for (int i = array.length - 1; i > 0; i--) {
  			index = random.nextInt(i + 1);
  			if (index != i) {
  				array[index] ^= array[i];
  				array[i] ^= array[index];
  				array[index] ^= array[i];
  			}
  		}
  	}
  
  	static class FastScanner {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer("");
  
  		String next() {
  			while (!st.hasMoreTokens()) {
  				try {
  					st = new StringTokenizer(br.readLine());
  				}
  				catch (IOException e) {
  					e.printStackTrace();
  				}
  			}
  			return st.nextToken();
  		}
  
  		int nextInt() {
  			return Integer.parseInt(next());
  		}
  
  		long[] readArrayLong(int n) {
  			long[] a = new long[n];
  			for (int i = 0; i < n; i++) {
  				a[i] = nextLong();
  			}
  			return a;
  		}
  
  		int[] readArrayInt(int n) {
  			int[] a = new int[n];
  			for (int i = 0; i < n; i++) {
  				a[i] = nextInt();
  			}
  			return a;
  		}
  
  		long nextLong() {
  			return Long.parseLong(next());
  		}
  
  		double nextDouble() {
  			return Double.parseDouble(next());
  		}
  	}
  
  	static class BIT {
  
  		// The size of the array holding the Fenwick tree values
  		final int N;
  
  		// This array contains the Fenwick tree ranges
  		private long[] tree;
  
  		// Create an empty Fenwick Tree with 'sz' parameter zero based.
  		public BIT(int sz) {
  			tree = new long[(N = sz + 1)];
  		}
  
  		// Construct a Fenwick tree with an initial set of values.
  		// The 'values' array MUST BE ONE BASED meaning values[0]
  		// does not get used, O(n) construction.
  		public BIT(long[] values) {
  
  			if (values == null) {
  				throw new IllegalArgumentException("Values array cannot be null!");
  			}
  
  			N = values.length;
  			values[0] = 0L;
  
  			// Make a clone of the values array since we manipulate
  			// the array in place destroying all its original content.
  			tree = values.clone();
  
  			for (int i = 1; i < N; i++) {
  				int parent = i + lsb(i);
  				if (parent < N) {
  					tree[parent] += tree[i];
  				}
  			}
  		}
  
  		// Returns the value of the least significant bit (LSB)
  		// lsb(108) = lsb(0b1101100) = 0b100 = 4
  		// lsb(104) = lsb(0b1101000) = 0b1000 = 8
  		// lsb(96) = lsb(0b1100000) = 0b100000 = 32
  		// lsb(64) = lsb(0b1000000) = 0b1000000 = 64
  		private static int lsb(int i) {
  
  			// Isolates the lowest one bit value
  			return i & -i;
  
  			// An alternative method is to use the Java's built in method
  			// return Integer.lowestOneBit(i);
  
  		}
  
  		// Computes the prefix sum from [1, i], O(log(n))
  		private long prefixSum(int i) {
  			long sum = 0L;
  			while (i != 0) {
  				sum += tree[i];
  				i &= ~lsb(i); // Equivalently, i -= lsb(i);
  			}
  			return sum;
  		}
  
  		// Returns the sum of the interval [left, right], O(log(n))
  		public long sum(int left, int right) {
  			if (right < left) {
  				throw new IllegalArgumentException("Make sure right >= left");
  			}
  			return prefixSum(right) - prefixSum(left - 1);
  		}
  
  		// Get the value at index i
  		public long get(int i) {
  			return sum(i, i);
  		}
  
  		// Add 'v' to index 'i', O(log(n))
  		public void add(int i, long v) {
  			while (i < N) {
  				tree[i] += v;
  				i += lsb(i);
  			}
  		}
  
  		// Set index i to be equal to v, O(log(n))
  		public void set(int i, long v) {
  			add(i, v - sum(i, i));
  		}
  
  		@Override
  		public String toString() {
  			return java.util.Arrays.toString(tree);
  		}
  	}
  }