题目描述

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$（数组中所有值两两不同）。你可以执行以下操作任意次：

• 选取一个下标 $i$（$1\le i\le n$）和一个整数 $x$，要求 $x\ge k$；
• 将 $a_i$ 替换为 $a_i \bmod x$（即取 $a_i$ 除以 $x$ 的余数）。

你的目标是使数组的所有元素都相同。在所有正整数 $k$ 中，确定存在使所有数组元素相等的上述运算的有限序列的最大值 $k$ 。

输入格式

第一行包含一个整数 $t（1 \le t \le 10^4）$，表示测试用例的数量。

随后是 $t$ 个测试用例，每个测试用例包含两行：

• 第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$），表示数组长度；
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^9$，且所有 $a_i$ 两两不同）。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数 —— 题目要求的最大的可行正整数 $k$。

样例输入

3
3
5 7 9
2
2 3
7
11 74 5 22 52 97 82

样例输出

5
2
6

说明

样例解释

• 第一个测试用例，数组为 $[5,7,9]$，最大的可行 $k$ 为 $5$；
• 第二个测试用例，数组为 $[2,3]$，最大的可行 $k$ 为 $2$；
• 第三个测试用例，数组为 $[11,74,5,22,52,97,82]$，最大的可行 $k$ 为 $6$。