Consider an infinite multiset $S$ containing elements $a_1, a_2, \dots, a_n$, where each type of element is available infinitely many times. We define a function $f(k)$ as follows: consider every subset $S'$ of $S$ with size exactly $k$, calculate the sum of the elements in $S'$, and find the greatest common divisor of these sums for all such subsets. 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$.

Find the maximum value of $f(k)$ and the smallest $k$ that achieves this maximum value. Specifically, if the maximum value does not exist, report "infinite".

Input

The input 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. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), representing the number of types of elements in $S$. The second line contains $n$ integers $a_1, a_2, \dots, 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

For each test case, if a maximum value of $f(k)$ exists, output two integers on a single line, representing the maximum value of $f(k)$ and the smallest $k$ that achieves this maximum.

Otherwise, output "infinite" (without quotes).

Examples

Input 1

2
2
3 6
2
2 2

Output 1

3 1
infinite

Input 2

2
3
1 4 7
4
4 16 28 34

Output 2

3 3
6 3

Note

For the first test case in Example 1, it can be observed that $f(k) = 3$ regardless of the value of $k$.

For the second test case in Example 1, $f(k) = 2k$, so $f$ grows infinitely and thus no maximum value exists.