B. Number Factorizationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputGiven 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.InputEach 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).OutputFor each test case, print the maximum value of \sum a_i \cdot p_i.ExampleInput
71001086413005619210000000002999999018Output
20
10
22
118
90
2
333333009
NoteIn 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.
71001086413005619210000000002999999018
20 10 22 118 90 2 333333009 
['greedy', 'math', 'number theory', '*1100']