A. Джо нужны деньги
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джо нужны деньги. Его друг Чендлер хотел бы дать Джо их, но не может сделать это в открытую, так как Джо слишком гордый. А потому Чендлер решил схитрить и предложил Джо сыграть в игру.

В этой игре Чендлер задает Джо массив $$$a_1, a_2, \dots, a_n$$$ ($$$n \geq 2$$$) из положительных целых чисел ($$$a_i \ge 1$$$).

Джо может применять к заданному массиву следующую операцию произвольное количество раз:

  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$$$.

В конце Джо получит количество денег, равное сумме элементов массива.

Определите наибольшее количество денег $$$\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}$$$).

Выходные данные

Для каждого набора данных выведите максимальное количество денег, которое может получить Джо, умноженное на $$$2022$$$.

Пример
Входные данные
3
3
2 3 2
2
1 3
3
1000000 1000000 1
Выходные данные
28308
8088
2022000000004044
Примечание

В первом наборе входных данных Джо может проделать следующие операции:

  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]$$$$$$
Сумма станет равна $$$14$$$ и будет максимально возможной. Ответ же равен $$$2022 \cdot 14 = 28308$$$.