乔伊缺钱。他的朋友钱德勒想借给乔伊一些钱,但不能直接给他,因为乔伊太骄傲了,无法接受。于是,为了欺骗他,钱德勒请乔伊玩一个游戏。
在这个游戏中,钱德勒给了乔伊一个正整数数组 $$$a_1, a_2, \dots, a_n$$$ ($$$n \geq 2$$$) ($$$a_i \ge 1$$$)。
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$$$ 替换为 $$$x$$$,将 $$$a_j$$$ 替换为 $$$y$$$。
最终,Joey 将获得等于最终数组元素之和的钱。
找出 Joey 可以获得的最大金额 $$$\mathrm{ans}$$$,但打印 $$$2022 \cdot \mathrm{ans}$$$。为什么要乘以$$$2022$$$?因为我们再也见不到它了!
保证数组$$$a$$$所有元素的乘积不超过$$$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}$$$)。
输出
对于每个测试用例,打印 Joey 可以获得的最大金额乘以 $$$2022$$$。
示例
输入 #1
3 3 2 3 2 2 1 3 3 1000000 1000000 1
输出 #1
28308 8088 2022000000004044
注意
在第一个测试用例中,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[x = 6,\; y = 1]{i = 1,\; j = 2} [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[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 1, 1]$$$$$$