Dada una secuencia de enteros $a_1,a_2,\cdots,a_n$ de longitud $n$ y un entero no negativo $k$, puedes realizar la siguiente operación como máximo una vez: elige dos enteros $l$ y $r$ tales que $1\le l\le r\le n$ y, para cada $l\le i\le r$, cambia $a_i$ por $(a_i+k)$.

Maximiza el máximo común divisor de toda la secuencia.

Se dice que un entero $g$ es un divisor común de toda la secuencia si $a_i$ es divisible por $g$ para todo $1\le i\le n$.

Entrada

Hay varios casos de prueba. La primera línea de la entrada contiene un entero $T$ que indica el número de casos de prueba. Para cada caso:

La primera línea contiene dos enteros $n$ y $k$ ($1\le n\le 3\times 10^5$, $0\le k\le 10^{18}$).

La segunda línea contiene $n$ enteros $a_1,a_2,\cdots,a_n$ ($1\le a_i\le 10^{18}$), que indican la secuencia.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $3\times 10^5$.

Salida

Para cada caso de prueba, imprime en una línea un entero que indique el máximo valor del máximo común divisor de toda la secuencia.

Ejemplos

Entrada 1

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

Salida 1

5
3

Nota

Para el primer caso del ejemplo, elige $l=2$ y $r=4$. La secuencia pasa a ser $\{5,5,15,10,10,555\}$. Su máximo común divisor es $5$.