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