長さ $n$ の整数列 $a_1,a_2,\cdots,a_n$ と非負整数 $k$ が与えられます。次の操作を高々 1 回行うことができます。$1\le l\le r\le n$ を満たす 2 つの整数 $l$ と $r$ を選び、すべての $l\le i\le r$ について $a_i$ を $(a_i+k)$ に変更します。

数列全体の最大公約数を最大化してください。

すべての $1\le i\le n$ について $a_i$ が $g$ で割り切れるとき、整数 $g$ を数列全体の公約数と呼びます。

入力

複数のテストケースがあります。入力の最初の行には、テストケースの数を表す整数 $T$ が与えられます。各テストケースについて:

最初の行には 2 つの整数 $n$ と $k$ ($1\le n\le 3\times 10^5$、$0\le k\le 10^{18}$) が与えられます。

2 行目には、数列を表す $n$ 個の整数 $a_1,a_2,\cdots,a_n$ ($1\le a_i\le 10^{18}$) が与えられます。

すべてのテストケースにわたる $n$ の合計は $3\times 10^5$ 以下であることが保証されます。

出力

各テストケースについて、数列全体の最大公約数の最大値を表す整数を 1 個、1 行に出力してください。

入出力例

入力 1

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

出力 1

5
3

注記

最初の例のテストケースでは、$l=2$ と $r=4$ を選びます。数列は $\{5,5,15,10,10,555\}$ となります。その最大公約数は $5$ です。