F. The Stones of Nim
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As you may know, the game of "Nim" is played with several piles of stones and two players alternating turns. During a turn, a player picks any non-empty pile and removes any positive number of stones from it; the one who is not able to make a move loses the game.

Alice wants to play Nim with the Mad Hatter on $$$n$$$ piles $$$s_1, s_2, \ldots, s_n$$$ with distinct positive number of stones, but they get bored because they've played the game too many times. Instead, Alice proposes the following variant:

  1. Alice will color each of the $$$n$$$ piles with one of $$$k$$$ colors.
  2. The Mad Hatter will keep several piles, all of which have the same color, and throw out the remaining piles. (Note that the Mad Hatter does not need to choose all piles of a given color.) The Mad Hatter should keep at least one pile.
  3. Alice and the Mad Hatter will play Nim on the remaining piles, with Alice going first.
Can you help Alice find a coloring of the piles into the minimum number of colors so that if both players play optimally, she will always win the final game of Nim?

Note that the input is given encoded; see the Input section for a description of it. Because of the encoding format, you will need to solve the given problem for each prefix $$$s_1, s_2, \ldots, s_i$$$. However, you will only output this coloring for the entire set of piles $$$s_1, s_2, \ldots, s_n$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 7000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0\le a_i\le 10^9$$$).

The $$$s_i$$$ are encoded: in particular, let $$$k_i$$$ be the minimum number of colors needed on the prefix $$$s_1, s_2, \ldots, s_{i-1}$$$ with $$$k_1 = 0$$$. Then, $$$s_i := a_i \oplus k_i$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. It is guaranteed that $$$1\le s_i \le 2n$$$ and that all $$$s_i$$$ are distinct.

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

Output

For each test case, on the first line, output $$$k$$$ — the minimum number of colors required for the full collection of piles.

On the $$$i$$$-th of the following $$$k$$$ lines, first print $$$\ell_i$$$ ($$$1 \leq \ell_i \leq n$$$) — the number of piles in the $$$i$$$-th color. Then print $$$\ell_i$$$ integers representing the sizes of the piles in the $$$i$$$-th color.

If there are multiple solutions, print any of them. We can show that an answer always exists for all prefixes.

Example
Input
3
3
1 3 2
6
1 3 2 6 7 10
9
18 12 17 3 6 4 13 11 9
Output
2
2 1 2
1 3
2
3 1 2 4
3 3 5 8
3
4 16 4 2 9
4 6 15 18 13
1 11
Note

In the first example, we can recover the input as follows:

  1. Since $$$k_1 = 0$$$, $$$s_1 := 1\oplus 0 = 1$$$.
  2. The minimum number of colors required when playing on $$$[1]$$$ is $$$1$$$, so $$$k_2 = 1$$$ (since Alice can immediately remove the single stone and win the game).
  3. Since $$$k_2 = 1$$$, $$$s_2 := 3\oplus 1 = 2$$$.
  4. The minimum number of colors required when playing on $$$[1, 2]$$$ is $$$1$$$, so $$$k_3 = 1$$$.
  5. Since $$$k_3 = 1$$$, $$$s_3 := 2\oplus 1 = 3$$$.

Thus, the piles have values $$$[1, 2, 3]$$$. We can show that the minimum number of colors required here is $$$2$$$, and a possible coloring is making the first and second pile color $$$1$$$, and the third pile color $$$2$$$.