Consider some positive integer x. Its prime factorization will be of form x = 2^{k_1} ⋅ 3^{k_2} ⋅ 5^{k_3} ⋅ ...

Let's call x elegant if the greatest common divisor of the sequence k_1, k_2, ... is equal to 1. For example, numbers 5 = 5^1, 12 = 2^2 ⋅ 3, 72 = 2^3 ⋅ 3^2 are elegant and numbers 8 = 2^3 (GCD = 3), 2500 = 2^2 ⋅ 5^4 (GCD = 2) are not.

Count the number of elegant integers from 2 to n.

Each testcase contains several values of n, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^5) — the number of values of n in the testcase.

Each of the next T lines contains a single integer n_i (2 ≤ n_i ≤ 10^{18}).

Output

Print T lines — the i-th line should contain the number of elegant numbers from 2 to n_i.

Example

Input

4
4
2
72
10


Output

2
1
61
6

Note

Here is the list of non-elegant numbers up to 10:

  * 4 = 2^2, GCD = 2; 
  * 8 = 2^3, GCD = 3; 
  * 9 = 3^2, GCD = 2. 



The rest have GCD = 1.
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws Exception {

		FastScanner scan = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);

		TreeSet<Long> t = new TreeSet<>();
		for(long i = 2; i < 1e6; i++) {
			if(isSquare((int) i)) continue;
			long j = i * i * i;
			while(true) {
				t.add(j);
				if(j > 1e18 / (i * i)) break;
				j *= i * i;
			}
		}
		a = new long[t.size()];
		for(int i = 0; i < a.length; i++) a[i] = t.pollFirst();
		
		for(int ttt = scan.nextInt(); ttt > 0; ttt--)
			pw.println(f(scan.nextLong()));
		
		pw.flush();
	}
	
	static long[] a;
	
	static long f(long n) {
		int s = 0, e = a.length, m;
		while(s < e) {
			m = (s + e) / 2;
			if(a[m] <= n) s = m+1;
			else e = m;
		}
		return n - sqrt(n) - e;
	}
	
	static boolean isSquare(int n) {
		long res = sqrt(n);
		return res * res == n;
	}
	
	static long sqrt(long n) {
		long res = (long) Math.sqrt(n) + 10;
		while(res * res > n)
			res--;
		return res;
	}

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() throws Exception {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}

		public FastScanner(String filename) throws Exception {
			br = new BufferedReader(new FileReader(filename));
			st = new StringTokenizer("");
		}

		public String nextLine() throws Exception {
			return br.readLine();
		}

		public String next() throws Exception {
			while (!st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws Exception {
			return Integer.parseInt(next());
		}

		public long nextLong() throws Exception {
			return Long.parseLong(next());
		}

		public double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}
	}
}