B. Факторизация числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$n$$$.

Рассмотрим все пары целочисленных массивов $$$a$$$ и $$$p$$$ одинаковой длины, такие что $$$n = \prod a_i^{p_i}$$$ (т.е. $$$a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots$$$)($$$a_i>1;p_i>0$$$) и $$$a_i$$$ является произведением некоторых (возможно, одного) различных простых чисел.

Например, для $$$n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 7^1$$$ пара массивов $$$a = [2, 7]$$$, $$$p = [2, 1]$$$ является корректной, а пара массивов $$$a = [4, 7]$$$, $$$p = [1, 1]$$$ нет, так как $$$4=2^2$$$ — произведение не различных простых чисел.

Ваша задача найти максимальное значение $$$\sum a_i \cdot p_i$$$ (т.е. $$$a_1\cdot p_1 + a_2\cdot p_2 + \ldots$$$) по всем возможным парам массивов $$$a$$$ и $$$p$$$. Обратите внимание, что вам не нужно минимизировать или максимизировать длину массива.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных содержит только одно целое число $$$n$$$ ($$$2 \le n \le 10^9$$$).

Выходные данные

Для каждого набора входных данных выведите максимальное значение $$$\sum a_i \cdot p_i$$$.

Пример
Входные данные
7
100
10
864
130056192
1000000000
2
999999018
Выходные данные
20
10
22
118
90
2
333333009
Примечание

В первом наборе входных данных $$$100 = 10^2$$$, так что $$$a = [10]$$$, $$$p = [2]$$$ и тогда $$$\sum a_i \cdot p_i$$$ достигает максимального значения $$$10\cdot 2 = 20$$$. Кроме того, $$$a = [100]$$$, $$$p = [1]$$$ не является корректной парой, так как $$$100$$$ не состоит из различных простых множителей.

Во втором наборе входных данных мы можем рассматривать $$$10$$$ как $$$10^1$$$, поэтому $$$a = [10]$$$, $$$p = [1]$$$. Обратите внимание, что когда $$$10 = 2^1\cdot 5^1$$$, $$$\sum a_i \cdot p_i = 7$$$.