G. 樱子的任务

每个测试的时间限制：2 秒
内存限制：256 兆字节

题目描述

樱子为你准备了一个任务：

她给你一个包含 $n$ 个整数的数组，并允许你选择 $i$ 和 $j$，满足 $i \neq j$ 且 $a_i \ge a_j$，然后将 $a_i$ 赋值为 $a_i - a_j$ 或 $a_i + a_j$。你可以任意次执行此操作，只要满足条件即可。

樱子问你，经过任意次操作后，数组的 $\operatorname{mex}_k$ 最大可能值是多少？

定义

$\operatorname{mex}_k$ 表示数组中缺失的第 $k$ 个非负整数。

例如：

• $\operatorname{mex}_1(\{1,2,3\}) = 0$，因为 $0$ 是第一个不在数组中的元素。
• $\operatorname{mex}_2(\{0,2,4\}) = 3$，因为 $3$ 是第二个不在数组中的元素。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \times 10^5$，$1 \le k \le 10^9$）—— 数组的长度和 $\operatorname{mex}_k$ 中的 $k$ 值。

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

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

输出格式

对于每个测试用例，输出经过操作后能够达到的最大 $\operatorname{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