Coprime Sequence

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

Do you know what is called ``Coprime Sequence''? That is a sequence consists of $n$ positive integers, and the GCD (Greatest Common Divisor) of them is equal to 1.
``Coprime Sequence'' is easy to find because of its restriction. But we can try to maximize the GCD of these integers by removing exactly one integer. Now given a sequence, please maximize the GCD of its elements.

Input

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.
In each test case, there is an integer $n(3\leq n\leq 100000)$ in the first line, denoting the number of integers in the sequence.
Then the following line consists of $n$ integers $a_1,a_2,...,a_n(1\leq a_i\leq 10^9)$, denoting the elements in the sequence.

Output

For each test case, print a single line containing a single integer, denoting the maximum GCD.

Sample Input

3 3 1 1 1 5 2 2 2 3 2 4 1 2 4 8

Sample Output

1 2 2

Hint

jiangzijing2015

Source

2017中国大学生程序设计竞赛 - 女生专场

提交代码