A11998. Relatively Prime Powers

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

Let's call $x$ elegant if the greatest common divisor of the sequence $k_1, k_2, \dots$ is equal to $1$ . For example, numbers $5 = 5^1$ , $12 = 2^2 \cdot 3$ , $72 = 2^3 \cdot 3^2$ are elegant and numbers $8 = 2^3$ ( $GCD = 3$ ), $2500 = 2^2 \cdot 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.

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

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

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

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$ .