CF1787B Number Factorization

Given an integer $ n $ . Consider all pairs of integer arrays $ a $ and $ p $ of the same length such that $ n = \prod a_i^{p_i} $ (i.e. $ a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots $ ) ( $ a_i>1;p_i>0 $ ) and $ a_i $ is the product of some (possibly one) distinct prime numbers. For example, for $ n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 7^1 $ the array pair $ a = [2, 7] $ , $ p = [2, 1] $ is correct, but the pair of arrays $ a = [4, 7] $ , $ p = [1, 1] $ is not, because $ 4=2^2 $ is a product of non-distinct prime numbers. Your task is to find the maximum value of $ \sum a_i \cdot p_i $ (i.e. $ a_1\cdot p_1 + a_2\cdot p_2 + \ldots $ ) over all possible pairs of arrays $ a $ and $ p $ . Note that you do not need to minimize or maximize the length of the arrays.

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Each test case contains only one integer $ n $ ( $ 2 \le n \le 10^9 $ ).

For each test case, print the maximum value of $ \sum a_i \cdot p_i $ .

In the first test case, $ 100 = 10^2 $ so that $ a = [10] $ , $ p = [2] $ when $ \sum a_i \cdot p_i $ hits the maximum value $ 10\cdot 2 = 20 $ . Also, $ a = [100] $ , $ p = [1] $ does not work since $ 100 $ is not made of distinct prime factors. In the second test case, we can consider $ 10 $ as $ 10^1 $ , so $ a = [10] $ , $ p = [1] $ . Notice that when $ 10 = 2^1\cdot 5^1 $ , $ \sum a_i \cdot p_i = 7 $ .