Сакурако подготовила для вас задачу:
Она дает вам массив из \(n\) целых чисел и позволяет выбрать \(i\) и \(j\) такие, что \(i \neq j\) и \(a_i \ge a_j\), а затем присвоить \(a_i = a_i - a_j\) или \(a_i = a_i + a_j\). Вы можете выполнить эту операцию любое количество раз для любых \(i\) и \(j\), если они удовлетворяют условиям.
Сакурако спрашивает вас, каково максимально возможное значение \(mex_k\)\(^{\text{∗}}\) массива после любого количества операций.
Выходные данные
Для каждого набора входных данных выведите максимальный \(mex_k\), которого возможно добиться с помощью операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 3
3
2 10
1 1
3 1
1 2 3
3 2
1 2 4
4 5
2 2 2 16
4 5
2 2 2 3
|
2
11
3
4
8
8
|