You are given an integer matrix of size n \times 2. Elements in the first column of matrix 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 .
Choose a sequence of 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 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.
The first line contains an integer – number of test cases.
The first line of each test case contains an integer – the number of rows in matrix .
The next lines of each test case contain two integers a_{i, 1} and a_{i, 2} – elements of the matrix.
1 \le t \le 10^6,
1 \le n \le 10^6,
the sum of over all test cases does not exceed 10^6.
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 – the number of moves.
On the next lines print the moves in the format k\ b_1\ b_2\ b_3 \dots b_k.
Example
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
goes to the position of ,
goes to the position of ,
goes to the position of ,
goes to the position of .
After the move, the matrix 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.