E. Greatest Common Divisor
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a positive integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$, you need to perform exactly $$$k$$$ operations. For each operation, you need to choose one element and increase its value by $$$1$$$.

Maximize the greatest common divisor of all elements after the operations.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^3$$$), indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le k \le 10^{12}$$$) indicating the length of the sequence and the number of operations.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) indicating the sequence.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$10^6$$$, the sum of $$$\max a_i$$$ of all test cases will not exceed $$$10^6$$$, and the sum of $$$k$$$ of all test cases will not exceed $$$10^{12}$$$.

Output

For each test case output one line containing one integer, indicating the maximum possible greatest common divisor of all elements after exactly $$$k$$$ operations.

Example
Input
2
3 6
2 9 8
3 7
2 9 8
Output
5
2
Note

For the first sample test case, we can change the sequence to $$$5, 10, 10$$$, and the greatest common divisor is $$$5$$$.

For the second sample test case, we can change the sequence to $$$6, 10, 10$$$, and the greatest common divisor is $$$2$$$.