如果一个排列的任何前缀（除了全排列本身）都不是一个排列，则称该排列是不可约的。例如，$[2, 3, 1]$ 和 $[4, 1, 2, 3]$ 是不可约的，而 $[2, 1, 3]$ 和 $[1, 3, 2]$ 则不是。

给定一个长度为 $n$ 的排列 $p$。在一次操作中，你可以选择任意两个相邻的位置并交换这两个位置上的值。

求将 $p$ 转换为一个不可约排列所需的最少操作次数，以及相应的操作序列。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 10^5$)。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。 每个测试用例的第二行包含 $n$ 个整数 $p_1, \dots, p_n$ ($1 \le p_i \le n$)。 保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，打印两行： 第一行打印一个整数 $k$：使 $p$ 变为不可约排列所需的最少操作次数。 第二行打印 $k$ 个用空格分隔的整数 $s_1, \dots, s_k$ ($1 \le s_i \le n - 1$)，其中 $s_i$ 和 $s_i + 1$ 是你打算交换的值所在的位置。操作将按照你输出的顺序依次执行。如果存在多种方案，打印其中任意一种即可。

样例

样例输入 1

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

样例输出 1

3
1 2 3
0
2
4 3