E. Relearn through Review
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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\leq n\leq 3 \times 10^5$$$, $$$0\leq k\leq 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.

Example
Input
2
6 2
5 3 13 8 10 555
3 0
3 6 9
Output
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$$$.