题目描述

给定一个整数 $n$。

考虑所有满足 $n = \prod a_i^{p_i}$ 的整数数组对 $a$ 和 $p$，其中 $a$ 和 $p$ 长度相同（即 $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$ 不是由互不相同的质数乘积得到的。

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

输入格式

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

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

输出格式

对于每个测试用例，输出最大的 $\sum a_i \cdot p_i$ 的值。

说明/提示

在第一个测试用例中，$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$。

由 ChatGPT 4.1 翻译

样例

7
100
10
864
130056192
1000000000
2
999999018

20
10
22
118
90
2
333333009