codeforces#P2008G. Sakurako's Task

Sakurako's Task

Description

Sakurako has prepared a task for you:

She gives you an array of $n$ integers and allows you to choose $i$ and $j$ such that $i \neq j$ and $a_i \ge a_j$, and then assign $a_i = a_i - a_j$ or $a_i = a_i + a_j$. You can perform this operation any number of times for any $i$ and $j$, as long as they satisfy the conditions.

Sakurako asks you what is the maximum possible value of $mex_k$$^{\text{∗}}$ of the array after any number of operations.

$^{\text{∗}}$$mex_k$ is the $k$-th non-negative integer that is absent in the array. For example, $mex_1(\{1,2,3 \})=0$, since $0$ is the first element that is not in the array, and $mex_2(\{0,2,4 \})=3$, since $3$ is the second element that is not in the array.

The first line contains a single integer $t$ ($1\le t\le 10^4$)  — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 2\cdot 10^5,1\le k\le 10^9$)  — the number of elements in the array and the value $k$ for $mex_k$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots,a_n$ ($1\le a_i\le 10^9$)  — the elements of the array.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

For each test case, output the maximum $mex_k$ that can be achieved through the operations.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$)  — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 2\cdot 10^5,1\le k\le 10^9$)  — the number of elements in the array and the value $k$ for $mex_k$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots,a_n$ ($1\le a_i\le 10^9$)  — the elements of the array.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output the maximum $mex_k$ that can be achieved through the operations.

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