Pebae 有一个整数数组 $a_1, a_2, \dots, a_n$。请帮她求出所有 $1 \le i, j \le n$ 中 $\gcd(a_i \oplus a_j, a_i \& a_j)$ 的最大值。此外，统计获得该最大值的数对数量。

这里，$\gcd(x, y)$ 是 $x$ 和 $y$ 的最大公约数，对于 $x \ge 0$ 有 $\gcd(x, 0) = x$，$\oplus$ 是按位异或运算符，$\&$ 是按位与运算符。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2^{19}$)。第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 16 \cdot n$)。

保证所有测试用例的 $n$ 之和不超过 $2^{20}$。

输出格式

对于每个测试用例，输出两个整数：最大值以及获得该最大值的数对数量。

样例

样例输入 1

4
4
1 9 1 9
1
0
3
0 0 1
7
12 2 3 0 110 1 69

样例输出 1

9 4
0 1
1 5
111 2