CF2008G.Sakurako's Task

樱子为你准备了一道题目：

她给你一个包含 $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$）——数组的元素个数和 $mex_k$ 的 $k$ 值。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\le a_i\le 10^9$）——数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，输出通过操作可以得到的最大 $mex_k$。

由 ChatGPT 4.1 翻译