Little Cyan Fish는 $1$부터 $n$까지의 정수로 이루어진 순열 $p_1, p_2, \ldots, p_n$을 가지고 있으며, 문제의 제목이 암시하듯 이를 오름차순으로 정렬하려고 합니다. 이번에 그가 수행할 수 있는 연산은 다음과 같습니다.

• 한 번의 연산에서 Little Cyan Fish는 $1 \le i < j \le n$을 만족하는 두 정수 $i$와 $j$를 선택하여 $p_i$와 $p_j$를 교환할 수 있습니다.

하지만 단순한 교환만으로 순열을 정렬하는 방법은 누구나 알고 있으므로, 당연히 이 문제가 요구하는 것은 그것이 아닙니다. 대신 Little Cyan Fish는 연산의 거리를 $j - i$로 정의합니다. 순열을 정렬하는 연산 수열에 대하여, 각 $1 \le d < n$에 대해 $a_d$를 거리가 $d$인 연산의 횟수라고 합시다.

순열을 정렬하는 모든 유한한 연산 수열 중에서, Little Cyan Fish는 사전순으로 가장 작은 수열 $(a_1, a_2, \ldots, a_{n-1})$을 찾고, 이를 달성하는 최대 $5n$번의 연산으로 이루어진 연산 수열을 구성하기를 원합니다.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 $T$ ($1 \le T \le 10^6$)가 주어집니다.

각 테스트 케이스에 대하여, 첫 번째 줄에는 순열의 길이를 나타내는 하나의 정수 $n$ ($2 \le n \le 10^6$)이 주어집니다. 두 번째 줄에는 순열을 나타내는 $n$개의 정수 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$)이 주어집니다. $p$는 길이가 $n$인 순열임이 보장됩니다.

모든 테스트 케이스에서 $n$의 합은 $10^6$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스에 대하여, 다음 형식으로 정답을 출력합니다.

각 테스트 케이스의 첫 번째 줄에는 사전순으로 가장 작은 수열을 나타내는 $n - 1$개의 정수 $a_1, a_2, \ldots, a_{n-1}$을 출력해야 합니다.

두 번째 줄에는 구성한 연산 수열의 연산 횟수를 나타내는 하나의 정수 $k$ ($0 \le k \le 5n$)를 출력해야 합니다.

다음 $k$개의 각 줄에는 해당 연산에서 선택한 인덱스를 나타내는 두 정수 $i$와 $j$ ($1 \le i < j \le n$)를 출력해야 합니다. 주어진 순서대로 연산을 수행했을 때 입력 순열이 정렬되어야 하며, 모든 $1 \le d < n$에 대하여 거리가 $d$인 연산이 정확히 $a_d$번 있어야 합니다.

최대 $5n$번의 연산으로 이루어진 최적의 연산 수열이 항상 존재함을 보일 수 있습니다. 올바른 연산 수열이 여러 개 존재하는 경우, 그중 아무것이나 출력해도 됩니다.

예제

입력 1

3
3
3 2 1
4
2 1 3 4
4
1 3 2 4

출력 1

0 1
1
1 3
0 1 2
3
1 4
2 4
1 4
0 3 2
5
1 3
1 4
2 4
1 4
1 3

참고

첫 번째 예제 테스트 케이스에서 Little Cyan Fish는 위치 $1$과 $3$을 교환합니다. 이는 거리가 $2$인 연산 한 번으로 순열을 정렬합니다.

두 번째 예제 테스트 케이스에서 최적의 연산 수열 중 하나는 $(1, 4)$, $(2, 4)$, $(1, 4)$입니다. 각 연산의 거리는 $3$, $2$, $3$이므로 결과 수열은 $(0, 1, 2)$가 됩니다.

세 번째 예제 테스트 케이스에서 최적의 연산 수열 중 하나는 $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$입니다. 거리별 연산 횟수는 $(0, 3, 2)$입니다.