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.

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.

见题面 Input 部分

见题面 Output 部分