{"raw_statement":[{"iden":"problem statement","content":"Given is a sequence $p$ which is a permutation of $(1,2, \\ldots, N)$. Initially, the $n$\\-th term of $p$ is $p_{n}$.\nYour objective is to sort $p$ in ascending order in at most $N^2$ _operations_. In one operation, you make the following change on $p$:\n\n*   In the $1$\\-st, $3$\\-rd, and subsequent **odd-numbered** operations, you choose an **odd number** $n$ between $1$ and $N-1$ (inclusive) to swap $p_n$ and $p_{n+1}$.\n*   In the $2$\\-nd, $4$\\-th, and subsequent **even-numbered** operations, you choose an **even number** $n$ between $2$ and $N-1$ (inclusive) to swap $p_n$ and $p_{n+1}$.\n\nWe can prove that the objective is always achievable under the Constraints of this problem. Find one sequence of operations that achieves the objective.\nYou will be given $T$ test cases and asked to solve each of them."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq T \\leq 250$\n*   $2 \\leq N \\leq 500$\n*   $1 \\leq p_i \\leq N$\n*   $p$ is a permutation of $(1,2,\\ldots,N)$.\n*   In one input file, the sum of $N$ does not exceed $500$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_{1}$\n$\\vdots$\n$\\mathrm{case}_{T}$\n\nEach case is in the following format:\n\n$N$\n$p_1$ $\\cdots$ $p_N$"},{"iden":"sample input 1","content":"2\n5\n2 1 3 5 4\n2\n1 2"},{"iden":"sample output 1","content":"2\n1 4\n0\n\n*   Here is the description for the $1$\\-st test case.\n    *   Choosing $1$ in the $1$\\-st operation makes $p = (1,2,3,5,4)$.\n    *   Choosing $4$ in the $2$\\-nd operation makes $p = (1,2,3,4,5)$.\n    *   Note that although $(1,4)$ is a valid sequence of operations, $(4, 1)$ is not.\n*   Also note that it is allowed to perform no operation, and it is not required to minimize the number of operations."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}