길이가 $n$인 정수 수열 $a_1,a_2,\cdots,a_n$과 음이 아닌 정수 $k$가 주어진다. 다음 연산을 최대 한 번 수행할 수 있다. $1\le l\le r\le n$을 만족하는 두 정수 $l$과 $r$을 선택한 뒤, 모든 $l\le i\le r$에 대해 $a_i$를 $(a_i+k)$로 바꾼다.

전체 수열의 최대공약수를 최대화하라.

모든 $1\le i\le n$에 대해 $a_i$가 $g$로 나누어떨어지면, 정수 $g$를 전체 수열의 공약수라고 한다.

입력

여러 테스트 케이스가 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스에 대해:

첫 번째 줄에는 두 정수 $n$과 $k$ ($1\le n\le 3\times 10^5$, $0\le k\le 10^{18}$)가 주어진다.

두 번째 줄에는 수열을 나타내는 $n$개의 정수 $a_1,a_2,\cdots,a_n$ ($1\le a_i\le 10^{18}$)이 주어진다.

모든 테스트 케이스에 대한 $n$의 합이 $3\times 10^5$를 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해 전체 수열의 최대공약수의 최댓값을 나타내는 정수 하나를 한 줄에 출력하라.

예제

입력 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$이다.