题目描述

考虑一个无限大的向量集 $S$，它的元素包含 $a_1, a_2, \cdots, a_n$，每种元素都有无限多。在此基础上，我们定义函数 $f(k)$ 如下：考虑 $S$ 的每个大小恰为 $k$ 的子集 $S'$，计算 $S'$ 中的元素之和，求出所有这些子集对应的和的最大公约数，作为 $f(k)$ 的值。形式化地，

$$f(k) = \gcd_{S' \subseteq S, |S'| = k} \left( \sum_{x \in S'} x \right)$$

例如，对于 $a = [3, 6]$，我们有

$$f(2) = \gcd(3 + 3, 3 + 6, 6 + 6) = 3$$

现在请你求出 $f(k)$ 的最大值，并求出取得最大值的最小的 $k$。特别地，如果最大值不存在，报告infinite。

输入格式

该题包含多组测试数据。输入第一行包含一个整数 $T$ ($1 \le T \le 4 \times 10^5$)，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示 $S$ 内数的种数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{18}$)，表示 $S$ 中的元素。

保证所有测试数据中的 $n$ 之和不超过 $4 \times 10^5$。

输出格式

对于每组数据，如果 $f(k)$ 存在最大值，则输出一行两个整数，分别表示 $f(k)$ 的最大值以及取得最大值时最小的 $k$。

否则输出 infinite（不包含引号）。

2
2
3 6
2
2 2

3 1
infinite

2
3
1 4 7
4
4 16 28 34

3 3
6 3

提示

对于样例一中的第一组数据，可以发现无论 $k$ 取多少，都有 $f(k)=3$。

对于样例一中的第二组数据，有 $f(k)=2k$，故 $f$ 会无限增长不存在最大值。