P15552 [CCPC 2025 哈尔滨站] k-子集和最大公约数问题

考虑一个无限大的向量集 $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``（不包含引号）。

对于样例一中的第一组数据，可以发现无论 $k$ 取多少，都有 $f(k)=3$。 对于样例一中的第二组数据，有 $f(k)=2k$，故 $f$ 会无限增长不存在最大值。