Дано целое число \(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\). Обратите внимание, что вам не нужно минимизировать или максимизировать длину массива.
Выходные данные
Для каждого набора входных данных выведите максимальное значение \(\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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
100
10
864
130056192
1000000000
2
999999018
|
20
10
22
118
90
2
333333009
|