Problem Description

Consider an infinite multiset $S$, whose elements include $a_1, a_2, \cdots, a_n$, and each type of element appears infinitely many times. Based on this, we define a function $f(k)$ as follows: for every subset $S'$ of $S$ with size exactly $k$, compute the sum of elements in $S'$. Take the greatest common divisor of all such sums, and use it as the value of $f(k)$. Formally,

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

For example, for $a = [3, 6]$, we have

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

Now please find the maximum value of $f(k)$, and the smallest $k$ that achieves this maximum. In particular, if the maximum value does not exist, report infinite.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 4 \times 10^5$), representing the number of test cases.

Then each test case is given as follows:

The first line contains an integer $n$ ($1 \le n \le 10^5$), representing the number of distinct values in $S$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{18}$), representing the elements in $S$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \times 10^5$.

Output Format

For each test case, if $f(k)$ has a maximum value, output one line with two integers: the maximum value of $f(k)$, and the smallest $k$ that achieves this maximum.

Otherwise output infinite (without quotes).

2
2
3 6
2
2 2

3 1
infinite

2
3
1 4 7
4
4 16 28 34

3 3
6 3

Hint

For the first test case in Sample 1, you can find that no matter what $k$ is, $f(k)=3$.

For the second test case in Sample 1, we have $f(k)=2k$, so $f$ grows without bound and the maximum value does not exist.

Translated by ChatGPT 5