配点 : $500$ 点

問題文

$(1,2, \ldots, N)$ を並び替えた数列 $p$ が与えられます。 はじめ、$p$ の第 $n$ 項は $p_{n}$ です。

あなたの目的は $N^2$ 回以下 操作 を行い $p$ を昇順に並び替えることです。 あなたは操作により以下のように $p$ を変更することができます。

• 奇数 回目の操作では $1$ 以上 $N-1$ 以下の 奇数 $n$ を選んで $p_n$ と $p_{n+1}$ を入れ替えます。
• 偶数 回目の操作では $2$ 以上 $N-1$ 以下の 偶数 $n$ を選んで $p_n$ と $p_{n+1}$ を入れ替えます。

この問題の制約下で必ず目的を達成できることが証明できます。 そのような操作列を $1$ つ求めてください。

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

制約

• 与えられる入力は全て整数
• $1 \leq T \leq 250$
• $2 \leq N \leq 500$
• $1 \leq p_i \leq N$
• $p$ は $(1,2,\ldots,N)$ を並び替えて得られる。
• $1$ つの入力ファイルにおいて $N$ の総和は $500$ を超えない。

入力

入力は以下の形式で標準入力から与えられる。

$T$

$\mathrm{case}_{1}$

$\vdots$

$\mathrm{case}_{T}$

各テストケースは以下の形式で与えられる。

$N$

$p_1$ $\cdots$ $p_N$

出力

$T$ 個のテストケースについて与えられた順番に以下の形式で答えを出力せよ。

$M$

$a_1$ $\cdots$ $a_M$

$M$ は操作列の長さを表し、$a_i$ は $i$ 回目の操作で選んだ整数を表す。

全てのテストケースにおいて目的が達成される操作列が出力されたならば正解となる。

2
5
2 1 3 5 4
2
1 2

2
1 4
0

• $1$ つ目のテストケースについて説明します。- $1$ 回目の操作で $1$ を選ぶと $p$ は $(1,2,3,5,4)$ となります。
  • $2$ 回目の操作で $4$ を選ぶと $p$ は $(1,2,3,4,5)$ となります。
  • $(1,4)$ は操作列として正しいですが、$(4,1)$ は操作列として正しくないことに注意してください。
• $1$ 回目の操作で $1$ を選ぶと $p$ は $(1,2,3,5,4)$ となります。
• $2$ 回目の操作で $4$ を選ぶと $p$ は $(1,2,3,4,5)$ となります。
• $(1,4)$ は操作列として正しいですが、$(4,1)$ は操作列として正しくないことに注意してください。
• 操作を $1$ 度も行わなくともよいこと、操作回数を最小にする必要はないことに注意してください。