Problem G
Crane

There are $n$ crates waiting to be loaded onto a ship. The crates are numbered $1, 2, \ldots , n$, the numbers determining the order of loading. Unfortunately, someone messed up the transit and the crates are standing in a row in an arbitrary order. As there is only limited space in the dock area, you must sort the crates by swapping some of them.

You are given a crane that works in the following way: you select a connected interval of crates of even length. The crane then exchanges the first half of the interval with the second half. The order inside both halves remains unchanged. Determine the sequence of crane moves that reorders the crates properly.

The crane’s software has a bug: the move counter is a $9$-based (not $10$-based, as you might think) integer with at most $6$ digits. Therefore, the crane stops working (and has to be serviced) after $9^6 = 531441$ moves. Your solution must fit within this limit.

Input

The first line of input contains the number of test cases $T$, $1 \leq T \leq 8$. The descriptions of the test cases follow:

Each test case starts with an integer $n$, $1 \leq n \leq 10\, 000$, denoting the number of crates. In the next line a permutation of numbers $\{ 1, 2, \ldots , n\} $ follows.

Output

For each test case print a single line containing $m$ – the number of swaps – followed by $m$ lines describing the swaps in the order in which they should be performed. A single swap is described by two numbers – the indices of the first and the last element in the interval to be exchanged. Do not follow the crane’s strange software design – use standard decimal numeral system.

2
6
5 4 6 3 2 1
5
1 2 3 4 5

5
1 2
4 5
5 6
4 5
1 6
0