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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Locale;
import java.util.StringTokenizer;

public class Solution2 implements Runnable {
	
	private static final int[] powers = buildPowers();
	private static final int[] mults = buildMults(powers);
	
	private PrintStream out;
	private BufferedReader in;
	private StringTokenizer st;
	
	public void solve() throws IOException {
		long time0 = System.currentTimeMillis();
		
		int t = nextInt();
		long[] n = new long[t];
		for (int i = 0; i < t; i++) {
			n[i] = nextLong();
		}
		long[] answer = solve(n);
		for (int i = 0; i < t; i++) {
			out.println(answer[i]);
		}
		
		
		System.err.println("time: " + (System.currentTimeMillis() - time0));
	}
	
	public long[] solve(long[] na) {
		long[] result = new long[na.length];
		Integer[] id = new Integer[na.length];
		for (int i = 0; i < na.length; i++) {
			id[i] = i;
		}
		Arrays.sort(id, new Comparator<Integer>() {
			@Override
			public int compare(Integer id0, Integer id1) {
				return Long.compare(na[id0], na[id1]);
			}
		});
		long[] vr = new long[powers.length];
		long[] vp = new long[powers.length];
		for (int ii = 0; ii < na.length; ii++) {
			int i = id[ii];
			long n = na[i];
			vr[0] = sqrt(n) + 1;
			vp[0] = vr[0] * vr[0];
			for (int j = 1; j < powers.length; j++) {
				while (vp[j] <= n) {
					vr[j]++;
					vp[j] = pow(vr[j], powers[j]);
				}
			}
			result[i] = n + 1;
			for (int j = 0; j < powers.length; j++) {
				result[i] += (vr[j] - 1) * mults[j];
			}
		}
		return result;
	}
	
	private long pow(long x, int p) {
		if (Math.pow(x, p) > 2000000000000000000L) {
			return 2000000000000000000L;
		}
		long result = 1;
		long xp = x;
		while (p > 0) {
			if (p % 2 == 1) {
				result *= xp;
			}
			xp = xp * xp;
			p /= 2;
		}
		return result;
	}

	private long sqrt(long n) {
		int left = 0;
		int right = Integer.MAX_VALUE;
		while (left + 1 < right) {
			int mid = (left + right) / 2;
			if (1L * mid * mid <= n) {
				left = mid;
			} else {
				right = mid;
			}
		}
		return left;
	}
	
	private static int[] buildMults(int[] powers) {
		int[] result = new int[powers.length];
		for (int i = 0; i < powers.length; i++) {
			result[i] = calcMult(powers[i]);
		}
		return result;
	}

	private static int calcMult(int p) {
		int result = 1;
		for (int i = 2; i * i <= p; i++) {
			if (p % i == 0) {
				p /= i;
				result *= -1;
			}
		}
		if (p > 1) {
			result *= -1;
		}
		return result;
	}

	private static int[] buildPowers() {
		List<Integer> list = new ArrayList<>();
		for (int i = 2; i < 60; i++) {
			if (goodPower(i)) {
				list.add(i);
			}
		}
		int[] result = new int[list.size()];
		for (int i = 0; i < result.length; i++) {
			result[i] = list.get(i);
		}
		return result;
	}

	private static boolean goodPower(int p) {
		for (int i = 2; i * i <= p; i++) {
			if (p % i == 0) {
				p /= i;
				if (p % i == 0) {
					return false;
				}
			}
		}
		return true;
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	
	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	public String next() throws IOException {
		while (!st.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) {
				return null;
			}
			st = new StringTokenizer(line);
		}
		return st.nextToken();
	}
	
	@Override
	public void run() {
		try {
			solve();
			out.close();
		} catch (Throwable e) {
			throw new RuntimeException(e);
		}
	}
	
	public Solution2(String name) throws IOException {
		Locale.setDefault(Locale.US);
		if (name == null) {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintStream(new BufferedOutputStream(System.out));
		} else {
			in = new BufferedReader(new InputStreamReader(new FileInputStream(name + ".in")));
			out = new PrintStream(new BufferedOutputStream(new FileOutputStream(name + ".out")));
		}
		st = new StringTokenizer("");
	}
	
	public static void main(String[] args) throws IOException {
		new Thread(new Solution2(null)).start();
	}
}
