I. Strange Sorting
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
We present an extremely simple sorting algorithm. It may look like it is obviously wrong, but we prove that it is in fact correct. $$$^{\text{∗}}$$$

After learning the strange sorting algorithm in the problem Paimon Sorting of The 2021 ICPC Asia Nanjing Regional Contest, Little Cyan Fish comes up with the following task.

Given a sequence $$$a_1, a_2, \cdots, a_n$$$ which is a permutation of $$$n$$$, your task is to sort the permutation in ascending order by applying the following operation for at most $$$\lfloor \frac{n}{2} \rfloor$$$ times: Choose two indices $$$l$$$ and $$$r$$$ satisfying $$$1 \le l \lt r \le n$$$ and $$$a_l \gt a_r$$$, and then sort $$$a_l, a_{l + 1}, \cdots, a_r$$$ in ascending order.

Recall that a permutation of $$$n$$$ is a sequence of length $$$n$$$, in which each integer from $$$1$$$ to $$$n$$$ (both inclusive) appears exactly once. Also recall that $$$\lfloor x \rfloor$$$ indicates the largest integer less than or equal to $$$x$$$.

$$$^{\text{∗}}$$$Stanley P. Y. Fung. Is this the simplest (and most surprising) sorting algorithm ever? arXiv:2110.01111

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) indicating the length of the permutation.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le n$$$) indicating the given permutation.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$10^4$$$.

Output

For each test case, first output one line containing one integer $$$k$$$ ($$$0 \le k \le \lfloor \frac{n}{2} \rfloor$$$) indicating the number of operations you're going to use. Then output $$$k$$$ lines, where the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ separated by a space, indicating the two indices you choose for the $$$i$$$-th operation.

It can be proven that the answer always exists. If there are multiple valid answers, you can output any of them.

Example
Input
3
6
2 3 4 6 5 1
5
1 2 3 4 5
3
2 3 1
Output
2
3 6
1 3
0
1
1 3
Note

For the first sample test case, after the $$$1$$$-st operation the permutation becomes $$$\{2, 3, 1, 4, 5, 6\}$$$, and after the $$$2$$$-nd operation the permutation becomes $$$\{1, 2, 3, 4, 5, 6\}$$$, which is in ascending order.