题目描述

有 $n$ 名学生，编号从 $1$ 到 $n$，他们需要为即将到来的黑客马拉松分组。你是学生 $1$，担任队长。学生 $i$ 的技能水平为 $a_i$。学生 $2$ 到 $n$ 按顺序从左到右站成一排。你可以选择站在任意两名学生之间，或者站在学生 $2$ 的左边，或者站在学生 $n$ 的右边。你不能改变这 $n-1$ 名学生的相对顺序。

你还需要选择分组的数量 $k$（$k > 1$ 且 $k$ 必须是 $n$ 的约数）来参加黑客马拉松。小组编号为 $1$ 到 $k$。在你选定自己的位置和 $k$ 的值之后，学生将按如下方式分组：

• 从左数第一名学生将被分到第 $1$ 组。
• 从左数第二名学生将被分到第 $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$ 应该互质。

2
4 1
2 1 2
3 10
4 3

1 1
10 3

提示

样例解释 #1

在第一个测试用例中，通过站在学生 $2$ 和 $3$ 之间（或学生 $3$ 和 $4$ 之间）并选择 $k=2$，第 1 组的技能水平为 $2+1$，第 2 组的技能水平为 $1+2$，因此比率为 $1/1$。

在第二个测试用例中，$k$ 的唯一选择是 $3$。