J. Alice and Bob
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice gives you an array $$$a$$$ of size $$$n$$$. You can perform the following operation any number of times (including zero):

  • Choose two distinct indexes $$$i$$$ and $$$j$$$, such that $$$a_j \le a_i$$$ and replace $$$a_i$$$ with $$$a_i-a_j$$$.

Bob being the troublemaker he is, orders you to change $$$\textbf{exactly one}$$$ element in the array before performing the above operation. Your goal is to maximize the gcd of the whole array, $$$gcd(a_1,a_2,...,a_n)$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$,$$$a_2$$$,…,$$$a_n$$$ ($$$1\le a_i\le 10^9$$$) — the elements of array $$$a$$$.

The sum of $$$n$$$ over all testcases does not exceed $$$10^6$$$.

Output

Output a single integer for each testcase — the maximum possible value of $$$gcd(a_1,a_2,...,a_n)$$$.

Example
Input
3
2
5 5
5
4 4 4 2 4
7
3 6 12 990 9 12 15
Output
5
4
3