Trung đang tham dự lớp học tin của thầy giáo Chung, và chủ đề của buổi học hôm nay là ước chung lớn nhất. Tiếng giảng bài của thầy bắt đầu vang lên.

"Với hai số nguyên ~a~ và ~b~ bất kì không đồng thời bằng ~0~, ước chung lớn nhất của ~a~ và ~b~ được định nghĩa là số nguyên ~x~ lớn nhất mà cả ~a~ và ~b~ đều chia hết cho ~x~. Ước chung lớn nhất của ~a~ và ~b~ được kí hiệu là ~\gcd(a, b)~, tương ứng với các chữ cái đầu tiên của khái niệm này khi dịch sang tiếng Anh (Greatest Common Divisor). Ví dụ, ~\gcd(8, 12) = 4~, ~\gcd(5, 7) = 1~, ~\gcd(0, 100) = 100~."

Đang say sưa giảng bài, thầy Chung bỗng phát hiện Trung đang nghịch điện thoại. Thấy vậy, thầy Chung trở nên tức giận và yêu cầu Trung phải giải được bài tập mà thầy đưa ra, nếu không thì cậu sẽ bị đuổi khỏi lớp. Ngặt nỗi, bài toán mà thầy Chung đưa ra lại vô cùng hóc búa:

"Cho dãy số ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Cậu hãy viết một đoạn mã để đổi chỗ các phần tử của dãy ~a~ theo một thứ tự bất kì, sao cho nếu định nghĩa dãy ~b~ gồm ước chung lớn nhất giữa các cặp số liên tiếp của dãy ~a~ (~b_i = \gcd(a_i, a_{i+1})~ với ~1 \le i < n~) thì giá trị lớn thứ nhì của dãy ~b~ là lớn nhất có thể. Cậu không cần phải in ra dãy ~a~ sau khi đổi chỗ, mà chỉ cần đưa ra giá trị lớn thứ nhì của dãy ~b~ tối đa tìm được."

Hãy giúp Trung giải bài toán trên, đồng thời giúp cậu thoát khỏi cơn thịnh nộ của thầy Chung nhé.

Input

Mỗi input sẽ gồm nhiều test cases. Dòng đầu tiên của input gồm số nguyên dương ~t~ (~1 \le t \le 1000~) — số test cases của bài toán. Sau đây là mô tả của các test cases.

Dòng đầu tiên của mỗi test case gồm số nguyên dương ~n~ (~3 \le n \le 100~) — số phần tử của dãy ~a~.

Dòng tiếp theo của mỗi test case gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 100~) — các phần tử của dãy ~a~.

Output

Với mỗi test case, in ra một số nguyên duy nhất là số lớn thứ nhì của dãy ~b~ tối đa tìm được.

Scoring

Số điểm nhận được nếu bạn giải thành công bài toán này là ~1250~ điểm.

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

Ở ví dụ thứ nhất, nếu ta đổi dãy ~a~ thành ~[20, 12, 6]~ thì dãy ~b~ ứng với dãy ~a~ là ~[\gcd(20, 12), \gcd(12, 6)] = [4, 6]~, phần tử lớn thứ nhì của dãy ~b~ là ~4~. Có thể chứng minh rằng không có cách sắp xếp nào cho kết quả tốt hơn.

Ở ví dụ thứ hai, nếu ta giữ nguyên dãy ~a~ như ban đầu (~[9, 6, 10, 5]~) thì dãy ~b~ ứng với dãy ~a~ là ~[3, 2, 5]~, phần tử lớn thứ nhì của dãy ~b~ là ~3~. Có thể chứng minh rằng không có cách sắp xếp nào cho kết quả tốt hơn.

Ở ví dụ thứ ba, mọi phần tử của dãy ~a~ đều là số nguyên tố nên với mọi cách đổi chỗ dãy ~a~ thì dãy ~b~ ứng với dãy ~a~ đều sẽ là ~[1, 1, 1, 1]~. Do đó phần tử lớn nhì của dãy ~b~ luôn là ~1~.