Busy Beaver is playing with his favorite blocks. There are $N$ blocks arranged in a row, each block having a color $c_i$. Busy Beaver hates seeing blocks of the same color next to each other, so he would like to rearrange the blocks into multiple rows, such that the blocks in each row are in the same ordering as they were in the original line, and no line has two consecutive blocks of the same color. Each of the $N$ original blocks should belong to exactly one of these rows.

Please help Busy Beaver determine an arrangement of blocks that uses the least possible number of lines.

Input

Each test contains multiple test cases. The first line of input contains a single integer $T$ $(1 \leq T \leq 10^5)$, the number of test cases. The description of each test case follows.

The first line of each test case contains a single positive integer $N$ ($1 \leq N \leq 2 \cdot 10^5$)~--- the number of blocks.

The second line contains $N$ space separated integers $c_i$ ($1 \leq c_i \leq 10^9$)~--- the color of the $i$th block.

It is guaranteed that the sum of $N$ across all test cases is no more than $2 \cdot 10^5$.

Output

For each test case, the first line of output should contain a single positive integer $k$, the minimum number of rows that Busy Beaver needs to rearrange the blocks to satisfy his conditions.

For each of the next $k$ lines, output the number of blocks in that row, as well as the indices of the blocks themselves, space separated. Each of the rows must be nonempty.

If there are multiple solutions with the same minimum number of rows needed, output any one of them.

Scoring

You will receive $30\%$ of the points for each subtask if your value of $k$ is correct, but the construction is incorrect. To receive this partial credit, you still need to output $k$ lines for each test describing some rearrangement of the blocks into $k$ nonempty rows.

For instance, the following output would receive partial credit on the sample input:

2
1 1
1 2
1
3 1 2 3
2
3 1 2 3
1 4

while the following does not:

2
2 1 2
0
1
0
2
1 1
1 2

There are two subtasks for this problem.

• ($30$ points): The sum of $N$ across all test cases does not exceed $5 \cdot 10^3$.
• ($70$ points): No additional constraints.

Example

Input

3
2
2 2
3
1 2 1
4
1 1 2 1

Output

2
1 1
1 2
1
3 1 2 3
2
1 1
3 2 3 4

Explanation

In the first test case, it is optimal to create two rows, each with one of the two blocks. It is impossible to use only one row, since the two blocks have the same color.

In the second test case, we can use one row to contain all three blocks.

In the third test case, it is optimal to create two rows, with one containing the first block and the second containing the remaining three blocks.