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