E. Oscar is All You Need
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Putata has a sequence $$$p$$$ of length $$$n$$$, where $$$p$$$ is a permutation of $$$1,2,\dots,n$$$. Budada can perform the following operation at most $$$2n + 1$$$ times:

  • Cut the sequence into three consecutive non-empty parts, and swap the first part and the last part. Formally, you should select two integers $$$x, y$$$ satisfying that $$$x \gt 0$$$, $$$y \gt 0$$$, $$$x+y \lt n$$$, and the sequence will change from $$$p_1,\dots, p_x,p_{x+1},\dots, p_{n-y}, p_{n-y+1},\dots, p_n$$$ to $$$p_{n-y+1}, \dots, p_n, p_{x+1}, \dots, p_{n-y}, p_1,\dots, p_x$$$.

Budada wants to make the lexicographical order of the permutation as small as possible after no more than $$$2n+1$$$ operations. Please help him find the way to perform operations so that the lexicographical order of the permutation is as small as possible.

A permutation is an array where each integer from $$$1$$$ to $$$s$$$ (where $$$s$$$ is the size of permutation) occurs exactly once.

A permutation $$$a$$$ is lexicographically smaller than a permutation $$$b$$$ if and only if the following condition holds:

  • Let $$$x$$$ be the smallest integer where $$$a_y=b_y$$$ holds for all $$$y\leq x$$$, then we have $$$x \lt n$$$ and $$$a_{x+1} \lt b_{x+1}$$$.
Input

The input contains several test cases.

The first line contains an integer $$$T$$$ ($$$1\leq T\leq 120$$$), denoting the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$3\leq n \leq 1000$$$), denoting the length of the permutation.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer is $$$p_i$$$ ($$$1\leq p_i \leq n$$$), denoting the permutation. It is guaranteed that $$$p$$$ is a permutation of $$$1,2,\dots, n$$$.

It is guaranteed that the sum of $$$n$$$ in all test cases will not exceed $$$1000$$$.

Output

For each test case, output one integer $$$m$$$ in the first line, denoting the number of operations. You should guarantee that $$$0\leq m\leq 2n + 1$$$.

Then output $$$m$$$ lines, each line contains two integers $$$x, y$$$, denoting one operation. You should guarantee that $$$0 \lt x$$$, $$$0 \lt y$$$, $$$x+y \lt n$$$.

Please notice that you do not have to minimize the number of operations.

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