Link with Nim Game
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Link is playing nim game with fried-chicken. If you don't know this game, here're the rules:

There are two players in this game, called Alice and Bob. The game starts with n piles of stones, the i-th pile contains a_i stones.

Alice and Bob take turns to play this game, Alice goes first. In each turn, the player should choose one pile of stones, and remove  stones from that pile. The player who can not operate loses.

Obviously, one of Alice and Bob has a winning strategy. If one player has a winning strategy, he or she wants to win in minimum turns. If one player will lose, he or she wants to lose in maximum turns.

Now, fried-chicken wonders, when both players uses the best strategy:

How many turns will take before the game ends?

How many kinds of operations can Alice do in the first turn under the restrictions above?

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases . Description of the test cases follows.

The first line contains a single integer .

The second line contains n integers .

It is guaranteed that the sum of n over all test cases does not exceed .

输出描述:

For each test case, output two integers in one line, which are the turns taken before the game ends and the kinds of operation Alice can do in the first turn under the restrictions above.
示例1

输入

复制
6
1
1
1
2
2
1 1
3
1 2 3
6
1 1 4 5 1 4
6
1 9 1 9 8 10

输出

复制
1 1
1 1
2 2
6 2
13 3
37 1