给定一个整数$$$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$$$ 是非不同素数的乘积。
你的任务是在所有可能的数组 $$$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$$$ 的最大值。
示例
输入 #1
7 100 10 864 130056192 1000000000 2 999999018
输出 #1
20 10 22 118 90 2 333333009
注意
在第一个测试用例中,$$$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$$$。