Solve the programming task below in a Python markdown code block.
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$.