write a go solution for Description:
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 Format:
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 Format:
Print T lines — the i-th line should contain the number of elegant numbers from 2 to n_i.

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.. Output only the code with no comments, explanation, or additional text.