有 $n$ 个板条箱等待装船。板条箱编号为 $1, 2, \dots, n$，这些数字决定了装载顺序。不幸的是，运输过程中出现了混乱，板条箱目前以任意顺序排成一行。由于码头区域空间有限，你必须通过交换其中的一些板条箱来对它们进行排序。

你拥有一台起重机，其工作方式如下：你选择一个长度为偶数的连续板条箱区间，起重机会将该区间的前半部分与后半部分进行交换。两个半部分内部的顺序保持不变。请确定能够将板条箱正确排序的起重机移动序列。

起重机的软件有一个缺陷：移动计数器是一个 9 进制（而不是你可能认为的 10 进制）整数，最多有 6 位。因此，起重机在 $9^6 = 531441$ 次移动后会停止工作（并需要维修）。你的解决方案必须符合此限制。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例以一个整数 $n$ 开始，$1 \le n \le 10\,000$，表示板条箱的数量。下一行包含一个数字 $\{1, 2, \dots, n\}$ 的排列。

输出格式

对于每个测试用例，输出一行包含 $m$（交换次数），随后是 $m$ 行，按执行顺序描述这些交换。单次交换由两个数字描述，即要交换区间的第一个和最后一个元素的索引。不要遵循起重机奇怪的软件设计——请使用标准的十进制数字系统。

样例

样例输入 1

2
6
5 4 6 3 2 1
5
1 2 3 4 5

样例输出 1

5
1 2
4 5
5 6
4 5
1 6
0