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.util.*;
import java.io.*;

public class f {
	long pow(long x, long y) {
		if(x == 0) return 0;
		long r = 1;
		while(y > 0) {
			if((y & 1) == 1) {
				if(x == 0 || (r * x) / x != r) return oo;
				r *= x;
			}
			y >>= 1;
			x *= x;
		}
		return r;
	}
	boolean check(long x, long k, long n) {
		return pow(x, k) <= n;
	}
	long kthRoot(long k, long n) {
		if(k == 1) return n;
		// reduce time by getting an estimate range
		long lo = (long) (Math.pow(n, 1.0 / k) - 100), hi = (long) (Math.pow(n, 1.0 / k) + 100);
		while(lo + 1 < hi) {
			long mid = (lo + hi) / 2;
			if(check(mid, k, n)) lo = mid;
			else hi = mid;
		}
		if(check(hi, k, n)) return hi;
		return lo;
	}
	void mobiusFunction() {
		int N = MAX, M = (int) (2 * N / Math.log(N)), len = 0;
		lp = new int[N];  pr = new int[M];  mobius = new int[N];
		mobius[1] = 1;
		for(int i = 2 ; i < N ; i++) {
			if(lp[i] == 0) {
				lp[i] = pr[len++] = i;
				mobius[i] = -1;
			}
			for(int j = 0 ; j < len && pr[j] <= lp[i] && i * pr[j] < N ; j++)
				lp[i * pr[j]] = pr[j];
		}
		for(int i = 2 ; i < N ; i++)
			if(mobius[i / lp[i]] != 0 && lp[i] != lp[i / lp[i]])
				mobius[i] = mobius[i / lp[i]] * -1;
	}
	final int MAXLOG = 62;
	final long oo = Long.MAX_VALUE;
	final int MAX = 200; // overkill but it's okay
	int[] lp, pr, mobius;
	public f() {
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		mobiusFunction();
		int q = scan.nextInt();
		long[][] query = new long[q][2];
		long[] results = new long[q];
		for(int qq = 0 ; qq < q ; qq++) {
			long n = scan.nextLong();
			query[qq][0] = n;  // query
			query[qq][1] = qq; // index
		}
		Arrays.sort(query, (a, b) -> Long.compare(b[0], a[0]));
		long[] kthRoots = new long[MAXLOG];
		long[] kthPowers = new long[MAXLOG];
		int bf = 6;
		for(int k = 1 ; k < MAXLOG ; k++) {
			kthRoots[k] = kthRoot(k, (long) 1e18);
			kthPowers[k] = pow(kthRoots[k], k);
		}
		for(int qq = 0 ; qq < q ; qq++) {
			long n = query[qq][0];
			for(int k = 1 ; k < bf ; k++) {
				kthRoots[k] = kthRoot(k, n);
				kthPowers[k] = pow(kthRoots[k], k);
			}
			for(int k = bf ; k < MAXLOG ; k++) {
				while(kthPowers[k] > n) {
					kthRoots[k]--;
					kthPowers[k] = pow(kthRoots[k], k);
				}
			}
			long res = 0;
			for(int k = 1 ; k < MAXLOG ; k++)
				res += (kthRoots[k] - 1) * mobius[k];
			results[(int) query[qq][1]] = res;
		}
		for(int qq = 0 ; qq < q ; qq++)
			out.println(results[qq]);
		out.close();
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { throw null; }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
	public static void main(String[] args) { new f(); }
}