小青魚有一個由 $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)$。