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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Edu50_F {

	static final int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 };

	public static void main(String[] args) throws IOException {
		int[] mult = new int[61];

		bSetLoop:
		for (int bSet = 1; bSet < (1 << 17); bSet++) {
			int bCnt = Integer.bitCount(bSet);

			int prod = 1;
			for (int i = 0; i < 17; i++) {
				if ((bSet & (1 << i)) != 0) {
					prod *= primes[i];
					if (prod > 60) {
						continue bSetLoop;
					}
				}
			}

			if ((bCnt & 1) == 1) {
				mult[prod]++;
			} else {
				mult[prod]--;
			}
		}

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter printer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		int nQ = Integer.parseInt(reader.readLine());

		// printer.println(cnt(51, 28316250877914579L));

		while (nQ-- > 0) {
			long qMax = Long.parseLong(reader.readLine());
			long ans = 0;
			for (int i = 2; i <= 60; i++) {
				// printer.println(i + ": " + cnt(i, qMax));
				ans += mult[i] * cnt(i, qMax);
			}
			printer.println(qMax - ans - 1);
		}
		printer.close();
	}

	static long cnt(int pow, long max) {
		long approx = (long) (Math.pow(max, 1.0 / pow));
		if (!greater(approx + 1, pow, max)) {
			return approx;
		} else if (!greater(approx, pow, max)) {
			return approx - 1;
		} else {
			return approx - 2;
		}
	}

	static boolean greater(long base, int pow, long bnd) {
		long stepA = bnd / base;
		long cur = 1;
		for (int i = 1; i <= pow - 1; i++) {
			cur *= base;
			if (cur > stepA) {
				return true;
			}
		}
		return false;
	}
}
