Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

F. Relatively Prime Powers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

Output

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

Example
Input
4427210
Output
21616
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$.