题目描述

• 题目翻译如下

Joey 很穷，因此他的朋友 Chandler 想要借给他一些钱。但是 Joey 的自尊心很强，为了不让他的自尊心受挫又能给他钱，Chandler 打算和他玩一个游戏。

在这个游戏中，Chandler 会给 Joey 一个数组 $a_1,a_2,\dots,a_n(n\ge 2,a_i \in \mathbb{Z^+})$。Joey 可以对这个数组进行如下的操作任意次：

1. 选择一对 $i$ 和 $j$ ( $1 \le i < j \le n)$ .
2. 选择两个整数 $x$ 和 $y$ ( $x, y \ge 1$ ) 使得 $x \cdot y = a_i \cdot a_j$ .
3. 将 $a_i, a_j$ 分别替换为 $x, y$.

最后， Joey 将得到的钱就是 $a$ 数组中所有值的和。即 Joey 所得的钱 $= \sum^{n}_{i=1}a_{i}$ .

你需要求出一个整数 $ans$，即 Joey 最多可以得到的钱，并输出 $2022 \cdot ans$ 。为什么要乘以 $2022$ 呢？因为我们再也见不到它了！（悲）

输入数据保证 $a$ 数组内所有数的乘积不超过 $10^{12}$，即 $\prod^{n}_{i=1}a_{i} \le 10^{12}$.

输入格式

输入包含多组测试数据。

• 第一行，一个整数 $T$，代表测试数据组数。
• 对于每一组测试数据，第一行为一个整数 $n(2 \leq n \leq 50)$，表示数组 $a$ 的长度。第二行为 $n$ 个整数 $a_1,a_2,\dots,a_n( 1 \leq a_i \leq 10^6 )$，表示 $a$ 数组。保证 $a$ 数组内所有数的乘积不超过 $10^{12}$，即 $\prod^{n}_{i=1}a_{i} \le 10^{12}$.

输出格式

共一行，一个整数，表示 Joey 最多可以得到的钱乘以 2022 后的值。

说明/提示

在测试样例的第一组测试数据中，Joey 可以这么做：

• 他选择 $i = 1 , j = 2$ (可得 $a[i] \cdot a[j] = 6$ ), 使 $x = 6, y = 1$ ，然后改变原数组使 $a[i] = x = 6 , a[j] = y = 1$ . 即原数组发生如下变化：

• 他选择 $i = 1 , j = 3$ (可得 $a[i] \cdot a[j] = 12$ ), 使 $x = 12 , y = 1$ 然后改变原数组使 $a[i] = x = 12 , a[j] = y = 1$ . 即原数组发生如下变化：

综上所述， Joey 可以得到的最多的钱即为 $12+1+1=14$ 元，所以输出应为 $14\times 2022 = 28308$.

样例

3
3
2 3 2
2
1 3
3
1000000 1000000 1

28308
8088
2022000000004044