F. XOR Sorting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a permutation$$$^\dagger$$$ $$$p$$$ of size $$$n$$$ that you are trying to sort. To do so, you may perform up to $$$20$$$ operations of the following form:

  • Select a subset of distinct indices $$$i_1, i_2, \cdots i_k$$$ such that the value of $$$p_{i_1} \oplus p_{i_2} \oplus \cdots \oplus p_{i_k}$$$, where $$$\oplus$$$ represents the bitwise XOR operation, is zero.
  • Sort the values of $$$p$$$ on indices $$$i_1, i_2, \cdots i_k$$$.

For example, for $$$p = [7, 3, 4, 1, 2, 6, 5]$$$, you could choose the indices $$$[2, 4, 5]$$$, since $$$p_2 \oplus p_4 \oplus p_5 = 1 \oplus 2 \oplus 3 = 0$$$. After this operation, $$$p$$$ would be equal to $$$[7, 1, 4, 2, 3, 6, 5]$$$.

It can be shown that if it is possible to sort the permutation in any number of operations, then it is possible in at most $$$20$$$.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2, 3, 1, 5, 4]$$$ is a permutation, but $$$[1, 2, 2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1, 3, 4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 2\cdot 10^5$$$) — 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$$$) — the size of the permutation.

The second line of each test case will contain $$$n$$$ distinct integers $$$p_1, p_2, \cdots p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of $$$p$$$.

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

Output

For each test case, if there is no solution, print $$$-1$$$.

Otherwise, the first line of output should contain a single integer $$$m$$$ ($$$0 \le m \le 20$$$) — the number of operations you will perform.

Each of the next $$$m$$$ lines should contain an integer $$$k$$$, followed by $$$k$$$ distinct integers $$$i_1, i_2, \cdots i_k$$$ ($$$1 \le i_j \le n$$$) — a description of the operations you will perform, in order. After these operations, the permutation should be sorted.

If there are multiple solutions, you can print any.

Example
Input
3
9
8 6 3 4 9 5 2 7 1
1
1
2
2 1
Output
3
6 1 2 4 5 7 9
4 5 7 8 9
3 3 5 6
0
-1
Note

In the first test case, $$$p=[8, 6, 3, 4, 9, 5, 2, 7, 1]$$$. We then perform the following operations, where the red numbers indicate the positions that we choose in the operation:

$$$$$$[8, 6, 3, 4, 9, 5, 2, 7, 1] \rightarrow [\color{red}8, \color{red}6, 3, \color{red}4, \color{red}9, 5, \color{red}2, 7, \color{red}1] \rightarrow [\color{red}1, \color{red}2, 3, \color{red}4, \color{red}6, 5, \color{red}8, 7, \color{red}9]$$$$$$ $$$$$$[1, 2, 3, 4, 6, 5, 8, 7, 9] \rightarrow [1, 2, 3, \color{red}4, \color{red}6, 5, \color{red}8, \color{red}7, \color{red}9] \rightarrow [1, 2, 3, \color{red}4, \color{red}6, 5, \color{red}7, \color{red}8, \color{red}9]$$$$$$ $$$$$$[1, 2, 3, 4, 6, 5, 7, 8, 9] \rightarrow [1, 2, \color{red}3, 4, \color{red}6, \color{red}5, 7, 8, 9] \rightarrow [1, 2, \color{red}3, 4, \color{red}5, \color{red}6, 7, 8, 9]$$$$$$

So this process successfully sorts the permutation.

In the second test case, $$$p$$$ is already sorted, so there is no need to perform any operations.

We can show that the permutation in the third test case cannot be sorted, no matter how many operations we perform.