Background

Special for beginners, ^_^

Description

小明每天都有零花钱，具体多少，按照理科爸爸的方法。 理科爸爸先生成n个数字ai，然后这些数字的最大公约数就是小明今天的零花钱。文科妈妈抖了个机灵，觉得如果允许删除一个数，剩下的数的最大公约数作为零花钱。这样小明为了获得更多的零花钱，计算量肯定比第一版方案大多了，从而能够更好的训练小明的计算能力。理科爸爸觉得文科妈妈今天特聪明，晚上特意下厨做了一桌好菜，犒劳了一下老婆大人。 然后小明想用一个比较好的办法求出最大值，来请教你帮他写代码搞定。

Format

Input

输入第一行是测试用例数量t（不超过10）。 对于每一个测试用例，第一行是一个n(3≤n≤100000)，表示序列中的正整数的数量。 下一行是n个正整数($1≤a_i≤10^{19}$)，表示序列中的每个数。

Output

对于每个测试例，输出最大的gcd。

Samples

3 
3 
1 1 1 
5 
2 2 2 3 2 
4 
1 3 9 27

1
2
3

Limitation

1s, 1024KiB for each test case.

source

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