Trung is attending Mr. Chung's computer science class, and today's topic is the greatest common divisor. The lecture begins:

"Given two integers ~a~ and ~b~ that are not both equal to zero, the greatest common divisor of ~a~ and ~b~ is defined as the largest integer ~x~ that both ~a~ and ~b~ are divisible by. The greatest common divisor of ~a~ and ~b~ is denoted as ~\gcd(a, b)~, corresponding to the first letters of this concept. For example, ~\gcd(8, 12) = 4~, ~\gcd(5, 7) = 1~, ~\gcd(0, 100) = 100~."

While Mr. Chung is teaching, he suddenly found out that Trung is playing with his phone. Seeing this, Mr. Chung becomes angry and demands that Trung solve a problem he assigns, or else he will be kicked out of the class. Unfortunately, the problem that Mr. Chung assigns is quite difficult:

"Given a sequence of ~n~ positive integers ~a_1, a_2, \ldots, a_n~, write a program to permute the elements of ~a~ in any order such that if we define a sequence ~b~ consisting of the greatest common divisors of consecutive pairs of ~a~ (~b_i = \gcd(a_i, a_{i+1})~ for ~1 \le i < n~), then the second largest value in ~b~ is as large as possible. You do not need to output the permuted sequence ~a~, just the maximum possible value of the second largest element in ~b~."

Help Trung solve this problem and escape Mr. Chung's wrath.

Input

Each input will consist of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 1000~) — the number of test cases. The following lines describe the test cases.

The first line of each test case contains a positive integer ~n~ (~3 \le n \le 100~) — the number of elements in the sequence ~a~.

The second line of each test case contains ~n~ positive integers ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 100~) — the elements of the sequence ~a~.

Output

For each test case, output a single integer — the second largest value in ~b~ that is as large as possible.

Scoring

The score for this problem is ~1250~ points.

Sample Input 1

3
3
20 6 12
4
9 6 10 5
5
2 3 5 7 11

Sample Output 1

4
3
1

Notes

In the first example, if we permute the sequence ~a~ to ~[20, 12, 6]~, then the sequence ~b~ corresponding to ~a~ is ~[\gcd(20, 12), \gcd(12, 6)] = [4, 6]~, and the second largest element in ~b~ is ~4~. It can be proven that there is no better way to permute the sequence.

In the second example, if we keep the sequence ~a~ as it is (~[9, 6, 10, 5]~), then the sequence ~b~ corresponding to ~a~ is ~[3, 2, 5]~, and the second largest element in ~b~ is ~3~. It can be proven that there is no better way to permute the sequence.

In the third example, all elements of ~a~ are prime numbers, so for any permutation of ~a~, the sequence ~b~ corresponding to ~a~ will always be ~[1, 1, 1, 1]~. Therefore, the second largest element in ~b~ is always ~1~.