There are ~n~ marble slots evenly distributed on a circular path. The slots are numbered from ~1~ to ~n~ in the clockwise direction. Additionally, there is a marble holder located at the center of the circular path, numbered ~n+1~.

Initially, with ~n~ marble slots on the circular path, slot ~i~ contains exactly one marble with color ~a_i~, and slot ~n+1~ is empty. The marbles are colored from ~1~ to ~n~, and no two marbles have the same color. You can move a marble from a slot containing a marble to an empty slot if the two slots are adjacent on the circular path, or if one of the slots is slot ~n+1~.

Find a sequence of marble moving operations to rearrange the marbles so that the marble with color ~i~ is in slot ~i~, while the number of operations does not exceed ~1500~.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 50~). The description of each test case is as follows.

The first line contains an integer ~n~ (~3 \le n \le 50~) – the number of marble slots on the circular path.

The second line consists of ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) – the colors of the marbles in the ~n~ marble slots on the circular path. Each marble color will appear exactly once.

Output

For each test case, output the answer in the following format:

On the first line, output an integer ~k~ (~0 \le k \le 1500~) – the number of marble moving operations to be performed.

On the ~i~-th line in the next ~k~ lines, output two integers ~s_i~ and ~t_i~ (~1 \le s_i, t_i \le n+1~, ~s_i \ne t_i~) describing the moving operation of the ~i~-th marble (from slot ~s_i~ to slot ~t_i~). Slot ~s_i~ must contain a marble, and slot ~t_i~ must be empty.

It can be proven that there always exists a way to rearrange the marbles satisfying the requirements of the problem statement.

Scoring

Sample Input 1

2
3
2 3 1
3
1 2 3

Sample Output 1

4
3 4
2 3
1 2
4 1
0

Notes

For the first test case, the diagram below illustrates a way to rearrange the marbles satisfying the requirements of the problem statement. The numbers outside the marble slots indicate the slot numbers, and the numbers inside indicate the color of the marble in the slot.

For the second test case, all marbles are already in their correct slots, so no marble moving operations are needed.