L. Blue server loves pets-pets-pets (Gold)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Splinter and his students

Splinter gave his students an array $$$a$$$ of $$$n$$$ integers. He would like the bitwise XOR of all elements to equal $$$0$$$.

To do so, the students may perform the following operation any number of times:

  • Choose an index $$$i$$$ ($$$1 \le i \le n$$$). Let $$$S$$$ be the XOR of all elements $$$a_j$$$ such that $$$a_j \neq a_i$$$. Replace $$$a_i$$$ with $$$S$$$. (If no such $$$j$$$ exists, replace $$$a_i$$$ with $$$0$$$.)

Find the minimum number of operations needed, and the number of distinct index sequences of that length that achieve it.

Two sequences are considered distinct if they differ in length or at any position.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — denotes the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — denotes the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — denotes the elements of the array.

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

Output

For each test case, output two integers: the minimum number of operations required, and the number of distinct sequences of that length that achieve the goal.

Example
Input
2
4
2 2 3 3
3
1 2 2
Output
0 1
1 1
Note

In the first test case, the array is initially $$$[2, 2, 3, 3]$$$. The XOR of all elements is $$$2 \oplus 2 \oplus 3 \oplus 3 = 0$$$. The minimum number of operations is $$$0$$$, and there is $$$1$$$ sequence of length $$$0$$$ (the empty sequence).

In the second test case, the array is initially $$$[1, 2, 2]$$$. The XOR of all elements is $$$1 \oplus 2 \oplus 2 = 1$$$. — If we choose $$$i=1$$$, $$$S$$$ is the XOR of elements not equal to $$$a_1=1$$$, which are $$$\{2, 2\}$$$. $$$S = 2 \oplus 2 = 0$$$. Replacing $$$a_1$$$ with $$$0$$$ gives $$$[0, 2, 2]$$$. The total XOR is $$$0 \oplus 2 \oplus 2 = 0$$$. This is one sequence of length $$$1$$$ starting with index $$$1$$$.