You are given an integer sequence $A=(A_{1}, A_{2},\dots, A_{N})$ of length N and an integer M such that 0 ≤ $M < \sum\limits_{i=1}^N A_{i}$.

An integer sequence $B=(B_{1}, B_{2},\dots, B_{N})$ of length N is called good if:

0 ≤ B_{i} ≤ A_{i} for each 1≤ i ≤ N
$B_{1}+ B_{2}+\dots+B_{N}=M$

Find the maximum value of $\gcd(A_{1}-B_{1},A_{2}-B_{2},\dots,A_{N}-B_{N})$ over all good sequences $B. Here, \gcd$ denotes the [greatest common divisor].

Note: $\gcd(a,b,c) = \gcd(a,\gcd(b,c))$ and $\gcd(a,0)=\gcd(0,a)=a$.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers N, M.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$.

------ Output Format ------

For each test case, print a single line containing one integer — the maximum value of $\gcd(A_{1}-B_{1},A_{2}-B_{2},\dots,A_{N}-B_{N})$ over all good sequences B.

------ Constraints ------

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
$0 ≤ M < \sum\limits_{i=1}^N A_{i}$

------ subtasks ------

Subtask #1 (50 points): $1 ≤ N ≤ 10^{4}$

Subtask #2 (50 points): Original constraints

----- Sample Input 1 ------
4
4 4
1 3 5 7
4 4
5 5 5 5
4 0
4 6 9 12
6 10
15 9 3 8 14 17
----- Sample Output 1 ------
3
4
1
7

----- explanation 1 ------
Test case $1$: The optimal strategy is to take $B=(1,0,2,1)$. The answer is $\gcd(1-1,3-0,5-2,7-1)=\gcd(0,3,3,6)=3$.

Test case $2$: The optimal strategy is to take $B=(1,1,1,1)$. The answer is $\gcd(5-1,5-1,5-1,5-1)=\gcd(4,4,4,4)=4$.

见题面

见题面