Sorted Pairs

Limits: 4 sec., 512 MiB

You are given an integer matrix \(a\) of size \(n \times 2\). Elements in the first column of matrix \(a\) form a permutation of values \(n+1, n+2, \dots, 2n\), and elements in the second column form a permutation of values \(1, 2, \dots, n\).

You can do any number of moves. In one move you can do the following.

• Choose any positive integer \(k\).

• Choose a sequence of \(k\) distinct numbers \((b_1, b_2, \dots, b_k)\), such that \(1 \le b_i \le 2n\) for all \(1 \le i \le k\).

• Cyclically shift all chosen numbers in the matrix (number \(b_1\) goes to the position of \(b_2\), number \(b_2\) goes to the position of \(b_3\), ..., number \(b_k\) goes to the position of \(b_1\)).

• Pay \(k\) coins.

What is the minimum number of coins you have to pay to get the left element smaller than the right element in every row? Note that it is not required to minimize the number of moves.

Input

The first line contains an integer \(t\) – number of test cases.

The first line of each test case contains an integer \(n\) – the number of rows in matrix \(a\).

The next \(n\) lines of each test case contain two integers \(a_{i, 1}\) and \(a_{i, 2}\) – elements of the matrix.

Output

For each test case, print the answer in the following format.

On the first line print the minimum number of coins.

On the second line print an integer \(m\) – the number of moves.

On the next \(m\) lines print the moves in the format \(k\ b_1\ b_2\ b_3 \dots b_k\).

Constraints

\(1 \le t \le 10^6\),

\(1 \le n \le 10^6\),

the sum of \(n\) over all test cases does not exceed \(10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
2 4 5 1 6 2 7 3 8 4 3 4 2 5 1 6 3	4 1 4 1 7 2 8 4 2 2 1 6 2 4 2

Notes

In the first sample, the matrix \(a = \begin{pmatrix} 5 & 1\\ 6 & 2\\ 7 & 3\\ 8 & 4 \end{pmatrix}\) is given.

One of the optimal strategies for this matrix is to make one move choosing \(k = 4, b = (1, 7, 2, 8)\). During this move

• \(1\) goes to the position of \(7\),

• \(7\) goes to the position of \(2\),

• \(2\) goes to the position of \(8\),

• \(8\) goes to the position of \(1\).

After the move, the matrix \(a\) becomes \(\begin{pmatrix} 5 & 8\\ 6 & 7\\ 1 & 3\\ 2 & 4 \end{pmatrix}\). Now, it holds that in every row, the left element is smaller than the right element.

The total number of paid coins is four.