Sequence GCD ~ WildLife-TK

You are given an integer sequence

$A = (A_{1}, A_{2}, \dots, A_{N})$ of length $N$ and an integer $M$ such that $0 \leq M < \sum_{i = 1}^{N} A_{i}$ .

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

$0 \leq B_{i} \leq A_{i}$ for each $1 \leq i \leq 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 \leq T \leq 10$
$1 \leq N \leq 10^{5}$
$1 \leq A_{i} \leq 10^{5}$
$0 \leq M < \sum_{i = 1}^{N} A_{i}$

Subtasks

Subtask #1 (50 points): $1 \leq N \leq 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

Explanation

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$ .

Sequence GCD