奇偶排序

时间限制：2s
空间限制：512MB

题目描述

给定一个 $1$ 到 $N$ 的排列 $p$。你需要在不超过 $N^2$ 次操作内将它排成升序。

第奇数次操作可以选择一个奇数 $i$，交换 $p_i$ 与 $p_{i+1}$；第偶数次操作可以选择一个偶数 $i$，交换 $p_i$ 与 $p_{i+1}$。每组数据的操作编号都从 $1$ 重新开始计算。在本题限制下总能完成目标。

有 $T$ 组测试数据，请分别构造一种合法操作序列。

输入格式

第一行一个整数 $T$。

每组数据先给出一个整数 $N$，下一行给出排列 $p_1,p_2,\ldots,p_N$。

输出格式

对每组数据，先输出操作次数 $M$，然后输出 $M$ 个整数 $a_1,a_2,\ldots,a_M$。其中 $a_k$ 表示第 $k$ 次操作交换当前位置 $a_k$ 与 $a_k+1$ 的元素。

输出必须满足 $0\le M\le N^2$、$1\le a_k<N$，并且 $a_k$ 与 $k$ 的奇偶性相同。执行全部操作后，排列必须升序。若 $M=0$，操作序列可以省略。

样例输入 1

2
5
2 1 3 5 4
2
1 2

样例输出 1

2
1 4
0

样例说明

第一组数据先交换位置 $1,2$，再交换位置 $4,5$，恰好分别满足奇数次选奇数位置、偶数次选偶数位置。第二组数据已经有序，不需要操作。

数据范围

• $1\le T\le 250$；
• $2\le N\le 500$；
• $p$ 是 $1,2,\ldots,N$ 的一个排列；
• 单个输入文件中所有 $N$ 之和不超过 $500$。

附件数据

• 子任务 1：输入　输出
• 子任务 2：输入　输出
• 子任务 3：输入　输出
• 子任务 4：输入　输出