小青魚有一個由 $1$ 到 $n$ 嘅整數組成嘅排列 $p_1, p_2, \ldots, p_n$，就好似題目個名噉講，佢想將呢個排列由細到大排好序。呢一次，佢可以做嘅操作如下。

• 喺一次操作入面，小青魚可以揀兩個滿足 $1 \le i < j \le n$ 嘅整數 $i$ 同 $j$，然後掉轉 $p_i$ 同 $p_j$。

不過，唔好講笑啦，個個都識點樣用簡單嘅掉轉嚟排好一個排列，所以呢道題目擺明唔係叫你做呢樣嘢。相反，小青魚將一次操作嘅距離定義做 $j - i$。對於一個可以將個排列排好序嘅操作序列，對每個 $1 \le d < n$，設 $a_d$ 代表距離係 $d$ 嘅操作次數。

喺所有可以將個排列排好序嘅有限操作序列入面，小青魚想你搵出字典序最細嘅序列 $(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$，啱啱好有 $a_d$ 次操作嘅距離係 $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

說明

喺第一組範例測試數據入面，小青魚掉轉位置 $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)$。