题目描述

藤丸立香要在终局特异点打败盖提亚，现在盖提亚给了他一个难题，你能用编程帮他解决这个问题吗

盖提亚给你准备了一个任务： 给你一个 $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$的最大可能值是多少

$mex_k$是数组中不存在的第$k$个非负整数。

例如 ：$mex_1(\{1,2,3\})=0$，因为0是第一个不在数组中的元素，而$mex_2(\{0,2,4\}=3$ 因为3是第二个不在数组中的元素

输入

第一行包括单个整数 $t$

每个测试用例的第一行包含两个整数 $n$ 和 $k$

保证所有测试用例中 $n$的总和不超过$2e5$,k最大为$1e9$

输出

对于每个测试用例，输出通过操作可以实现的最多 $mex_k$。

input

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

output

2
11
3
4
8
8