有 $n$ 名学生，编号从 1 到 $n$，他们需要为即将到来的黑客马拉松组队。你是 1 号学生，也是学生队长。学生 $i$ 的技能水平为 $a_i$。
学生 2 到 $n$ 按从左到右的顺序排成一列。你可以选择站在任意两个学生之间、2 号学生的左侧，或者 $n$ 号学生的右侧。你不能改变这 $n - 1$ 名学生的顺序。
你还可以选择参加黑客马拉松的组数 $k$（$k > 1$ 且 $k$ 必须是 $n$ 的约数）。小组编号从 1 到 $k$。在你选定位置和 $k$ 的值后，学生将按以下方式分组：
- 从左往右数第 1 名学生被分配到第 1 组。
- 从左往右数第 2 名学生被分配到第 2 组。
- ...
- 从左往右数第 $k$ 名学生被分配到第 $k$ 组。
- 从左往右数第 $k + 1$ 名学生被分配到第 1 组。
- 从左往右数第 $k + 2$ 名学生被分配到第 2 组。
- ...
- 从左往右数第 $n$ 名学生被分配到第 $k$ 组。
形式化地，对于每个 $j$（$1 \le j \le k$）和每个 $i$（$0 \le i < n/k$），从左往右数第 $(i \times k + j)$ 名学生将被分配到第 $j$ 组。可以证明，每名学生都会被分配到且仅被分配到一个小组，且所有小组的人数相同。
小组的技能水平是该组内所有学生技能水平之和。通过最优地选择你的站位以及组数 $k$，你希望最小化比值 $x_{\max}/x_{\min}$，其中：
- $x_{\max}$ 是技能水平最高的小组的技能水平，
- $x_{\min}$ 是技能水平最低的小组的技能水平。
输入格式
输入的第一行包含一个整数 $t$（$1 \le t \le 100\,000$），表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例的格式如下：
测试用例的第一行包含两个整数 $n$ 和 $a_1$（$2 \le n \le 10^6$；$1 \le a_1 \le 1000$）。下一行包含 $n - 1$ 个整数 $a_2, a_3, \dots, a_n$（对于所有 $i$，$1 \le a_i \le 1000$）。
单个输入文件中所有测试用例的 $n$ 之和不超过 $10^6$。
输出格式
对于每个测试用例，输出一行，包含两个正整数 $p$ 和 $q$，使得最小比值为 $p/q$。分数 $p/q$ 应为最简分数。换句话说，$p$ 和 $q$ 应互质。
样例
输入 1
2 4 1 2 1 2 3 10 4 3
输出 1
1 1 10 3
说明
在第一个测试用例中，通过站在学生 2 和 3 之间（或学生 3 和 4 之间）并选择 $k = 2$，第 1 组的技能水平为 $2+1$，第 2 组的技能水平为 $1+2$，因此比值为 $1/1$。
在第二个测试用例中，$k$ 的唯一选择是 3。