CF1731A.Joey Takes Money

Joey is low on money. His friend Chandler wants to lend Joey some money, but can't give him directly, as Joey is too proud of himself to accept it. So, in order to trick him, Chandler asks Joey to play a game.

In this game, Chandler gives Joey an array $a_1, a_2, \dots, a_n$ ($n \geq 2$) of positive integers ($a_i \ge 1$).

Joey can perform the following operation on the array any number of times:

1. Take two indices $i$ and $j$ ($1 \le i \lt j \le n)$.
2. Choose two integers $x$ and $y$ ($x, y \ge 1$) such that $x \cdot y = a_i \cdot a_j$.
3. Replace $a_i$ by $x$ and $a_j$ by $y$.

In the end, Joey will get the money equal to the sum of elements of the final array.

Find the maximum amount of money $\mathrm{ans}$ Joey can get but print $2022 \cdot \mathrm{ans}$. Why multiplied by $2022$? Because we are never gonna see it again!

It is guaranteed that the product of all the elements of the array $a$ doesn't exceed $10^{12}$.

乔伊手头很紧。他的朋友钱德勒想借给乔伊一些钱，但又不能直接给他，因为乔伊太骄傲，不愿接受施舍。于是，为了“骗”他，钱德勒邀请乔伊玩一个游戏。

在这个游戏中，钱德勒给乔伊一个长度为 $n$（$n \geq 2$）的正整数数组 $a_1, a_2, \dots, a_n$（每个 $a_i \ge 1$）。

乔伊可以对这个数组执行以下操作任意多次：

1. 选取两个下标 $i$ 和 $j$（满足 $1 \le i \lt j \le n$）；
2. 选取两个正整数 $x$ 和 $y$（即 $x, y \ge 1$），使得 $x \cdot y = a_i \cdot a_j$；
3. 将 $a_i$ 替换为 $x$，同时将 $a_j$ 替换为 $y$。

最终，乔伊获得的钱数等于最终数组中所有元素的和。

请找出乔伊能获得的最大金额 $\mathrm{ans}$，但输出结果需为 $2022 \cdot \mathrm{ans}$。为什么乘以 $2022$？因为——我们再也不会见到它了！

保证数组 $a$ 中所有元素的乘积不超过 $10^{12}$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 4000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 50$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^6$) — the array itself.

It's guaranteed that the product of all $a_i$ doesn't exceed $10^{12}$ (i. e. $a_1 \cdot a_2 \cdot \ldots \cdot a_n \le 10^{12}$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 4000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 50$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）—— 数组本身。

保证所有 $a_i$ 的乘积不超过 $10^{12}$（即 $a_1 \cdot a_2 \cdot \ldots \cdot a_n \le 10^{12}$）。

For each test case, print the maximum money Joey can get multiplied by $2022$.

对于每个测试用例，输出 Joey 能获得的最大金额乘以 $2022$ 的结果。

In the first test case, Joey can do the following:

1. He chooses $i = 1$ and $j = 2$ (so he has $a[i] \cdot a[j] = 6$), chooses $x = 6$ and $y = 1$ and makes $a[i] = 6$ and $a[j] = 1$. $$[2, 3, 2] \xrightarrow[x = 6,\; y = 1]{i = 1,\; j = 2} [6, 1, 2]$$
2. He chooses $i = 1$ and $j = 3$ (so he has $a[i] \cdot a[j] = 12$), chooses $x = 12$ and $y = 1$ and makes $a[i] = 12$ and $a[j] = 1$. $$[6, 1, 2] \xrightarrow[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 1, 1]$$

The sum is $14$ which is the maximum of all possible sums. The answer is $2022 \cdot 14 = 28308$.

在第一个测试用例中，Joey 可以执行以下操作：

1. 他选择 $i = 1$ 和 $j = 2$（此时有 $a[i] \cdot a[j] = 6$），再选择 $x = 6$ 和 $y = 1$，并将 $a[i]$ 修改为 $6$、$a[j]$ 修改为 $1$。

$$[2, 3, 2] \xrightarrow[i = 1,\; j = 2]{x = 6,\; y = 1} [6, 1, 2]$$

2. 他选择 $i = 1$ 和 $j = 3$（此时有 $a[i] \cdot a[j] = 12$），再选择 $x = 12$ 和 $y = 1$，并将 $a[i]$ 修改为 $12$、$a[j]$ 修改为 $1$。

$$[6, 1, 2] \xrightarrow[i = 1,\; j = 3]{x = 12,\; y = 1} [12, 1, 1]$$

此时数组元素之和为 $14$，是所有可能方案中的最大值。答案为 $2022 \cdot 14 = 28308$。