Given an integer sequence $a_1,a_2,\cdots,a_n$ of length $n$ and a non-negative integer $k$, you can perform the following operation at most once: Choose two integers $l$ and $r$ such that $1\le l\le r\le n$, then for each $l\le i\le r$, change $a_i$ into $(a_i+k)$.

Maximize the greatest common divisor of the whole sequence.

An integer $g$ is said to be the common divisor of the whole sequence, if $a_i$ is divisible by $g$ for all $1\le i\le n$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($1\le n\le 3\times 10^5$, $0\le k\le 10^{18}$).

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ($1\le a_i\le 10^{18}$) indicating the sequence.

It's guaranteed that the sum of $n$ of all test cases does not exceed $3\times 10^5$.

Output

For each test case output one line containing one integer indicating the maximum greatest common divisor of the whole sequence.

Examples

Input 1

2
6 2
5 3 13 8 10 555
3 0
3 6 9

Output 1

5
3

Note

For the first sample test case, choose $l=2$ and $r=4$. The sequence will become $\{5,5,15,10,10,555\}$. Its greatest common divisor is $5$.