Little Cyan Fish は $1$ から $n$ までの整数からなる順列 $p_1, p_2, \ldots, p_n$ を持っており、問題のタイトルが示す通り、これを昇順にソートしたいと考えています。今回、彼が行える操作は次の通りです。

• 1 回の操作で、Little Cyan Fish は $1 \le i < j \le n$ を満たす 2 つの整数 $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$ 回の操作からなる操作列を 1 つ構築してほしいと考えています。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す 1 つの整数 $T$ ($1 \le T \le 10^6$) が与えられます。

各テストケースについて、1 行目には順列の長さを表す 1 つの整数 $n$ ($2 \le n \le 10^6$) が与えられます。2 行目には順列を表す $n$ 個の整数 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) が与えられます。$p$ は長さ $n$ の順列であることが保証されます。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証されます。

出力

各テストケースについて、以下の形式で答えを出力してください。

各テストケースの 1 行目には、辞書順最小の列を表す $n - 1$ 個の整数 $a_1, a_2, \ldots, a_{n-1}$ を出力してください。

2 行目には、構築した操作列に含まれる操作の回数を表す 1 つの整数 $k$ ($0 \le k \le 5n$) を出力してください。

続く $k$ 行にはそれぞれ、対応する操作で選んだ添字を表す 2 つの整数 $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

注記

1 つ目のサンプルテストケースでは、Little Cyan Fish は位置 $1$ と $3$ を交換します。これにより、距離 $2$ の操作 1 回で順列がソートされます。

2 つ目のサンプルテストケースでは、最適な操作列の 1 つは $(1, 4)$、$(2, 4)$、$(1, 4)$ です。距離はそれぞれ $3$、$2$、$3$ であるため、得られる列は $(0, 1, 2)$ となります。

3 つ目のサンプルテストケースでは、最適な操作列の 1 つは $(2, 4)$、$(1, 4)$、$(1, 3)$、$(1, 4)$、$(2, 4)$ です。各距離の操作回数は $(0, 3, 2)$ となります。