← 返回题目列表

Codeforces · 2092/A

A. 卡米尔卡和羊

中文机器翻译题面 查看原题

卡米尔卡有一群 $$$n$$$ 羊,其中第 $$$i$$$ 的美丽等级为 $$$a_i$$$。所有 $$$a_i$$$ 都是不同的。早晨到了,这意味着它们需要喂食。卡米尔卡可以选择一个非负整数 $$$d$$$ 并给每只羊 $$$d$$$ 一堆草。之后,每只羊的美丽等级都会增加$$$d$$$。

晚上,卡米尔卡必须选择 正好两个 羊并把它们带到山上。如果这两只羊的美丽程度是 $$$x$$$ 和 $$$y$$$(喂饱后),那么卡米尔卡的 高兴 步行所得的 等于 $$$\gcd(x, y)$$$,其中 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

任务是找到卡米尔卡可以从步行中获得最大可能的乐趣。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$),测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$),即卡米尔卡拥有的羊的数量。

每个测试用例的第二行包含 $$$n$$$ 不同 整数 $$$a_1, a_2, \ldots, a_n \ (1 \le a_i \le 10^9)$$$ — 羊的美丽等级。

保证所有 $$$a_i$$$ 都是不同的。

输出

对于每个测试用例,输出一个整数:卡米尔卡从步行中获得的最大可能乐趣。

示例

输入
复制

4
2
1 3
5
5 4 3 2 1
3
5 6 7
3
1 11 10

输出
复制

2
4
2
10

注意

在第一个测试用例中,$$$d=1$$$ 有效。在这种情况下,快乐是$$$\gcd(1+1, \ 1+3)=\gcd(2, \ 4)=2$$$。可见无法得到更大的答案。

在第二个测试用例中,我们采用$$$d=3$$$。在这种情况下,快乐是$$$\gcd(1+3, \ 5+3)=\gcd(4, \ 8)=4$$$。因此,对于这个测试用例,答案是 $$$4$$$。