Сакурако подготовила для вас задачу:
Она дает вам массив из \(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{∗}}\) массива после любого количества операций.
\(^{\text{∗}}\)\(mex_k\) — это \(k\)-е целое неотрицательное число, которого нет в массиве. Например, \(mex_1(\{1,2,3 \})=0\), так как \(0\) — первый элемент, которого нет в массиве, и \(mex_2(\{0,2,4 \})=3\), так как \(3\) — второй элемент, которого нет в массиве.
Первая строка содержит одно целое число \(t\) (\(1\le t\le 10^4\)) — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа \(n\) и \(k\) (\(1\le n\le 2\cdot 10^5,1\le k\le 10^9\)) — количество элементов массива и параметр \(k\) для \(mex_k\).
Вторая строка каждого набора содержит \(n\) целых чисел \(a_1, a_2, \dots,a_n\) (\(1\le a_i\le 10^9\)) — элементы массива.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(2\cdot 10^5\).
Для каждого набора входных данных выведите максимальный \(mex_k\), которого возможно добиться с помощью операций.
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач