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 \gt 1;p_i \gt 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.

给定一个整数 $n$。

考虑所有满足以下条件的整数数组对 $(a, p)$（两数组长度相同）：

$$n = \prod a_i^{p_i} \quad \text{（即 } a_1^{p_1} \cdot a_2^{p_2} \cdot \ldots\text{）},$$

其中 $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$ 是非互异素数的乘积（素因子 $2$ 重复出现）。

你的任务是：在所有可能的数组对 $(a, p)$ 中，求 $\sum a_i \cdot p_i$（即 $a_1 \cdot p_1 + a_2 \cdot p_2 + \ldots$）的最大值。注意：你无需最小化或最大化数组的长度。

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例仅包含一个整数 $n$（$2 \le n \le 10^9$）。

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

对于每个测试用例，输出 $\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$.

在第一个测试用例中，$100 = 10^2$，因此当 $\sum a_i \cdot p_i$ 取得最大值 $10\cdot 2 = 20$ 时，有 $a = [10]$，$p = [2]$。另外，$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$。