← 返回题目列表

Codeforces · 1787/B

B. 数字分解

中文机器翻译题面 查看原题

给定一个整数$$$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$$$。