두 원소 바꾸기

길이 $N$의 순열 $A=[A_1,A_2,\cdots,A_N]$이 주어진다. 다음 연산을 원하는 만큼 수행할 수 있다.

• 두 정수 $i,j$를 고른다. $1\leq i<j\leq N$이어야 한다.
• 부분 수열 $A_i,A_{i+1},\cdots,A_j$에서 가장 작은 원소가 있는 위치와 두 번째로 작은 원소가 있는 위치의 값을 서로 바꾼다.

순열을 오름차순으로 만들기 위한 연산 횟수의 최솟값과, 그 최솟값을 달성하는 연산 방법 하나를 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

각 테스트 케이스마다 첫 줄에 필요한 최소 연산 횟수 $Q$를 출력한다.

다음 $Q$개의 줄에 수행할 연산의 $i,j$를 순서대로 출력한다. 가능한 최적 연산 방법이 여러 가지라면 아무거나 출력해도 된다.

• $1 \leq T \leq 1\,000$.
• $1 \leq N \leq 1\,000$.
• $A$는 $1,2,\cdots,N$의 순열이다.
• 모든 테스트 케이스에 대한 $N$의 합은 $1\,000$ 이하이다.