まず、以下の問題を考えます。

\(0\) と \(1\) からなる長さ \(N\) の整数列 \(A=(A_1,A_2,\ldots,A_N)\) が与えられる。\(A\) を適切に並び替えることで、\(\displaystyle \sum_{i=1}^N\bigoplus_{1\le j\le i}A_j\) の値を最小化せよ。

\(\displaystyle \sum_{i=1}^N\bigoplus_{1\le j\le i}A_j\) の値は、\(A_i=1\) を満たす \(i\) を \(C_1 < C_2 < \ldots < C_{|C|}\) として \(\displaystyle \sum_{i=1}^{\left\lfloor\frac{|C|+1}2\right\rfloor} (C_{2i}-C_{2i-1})\) （ただし \(C_{|C|+1}=N+1\) とする）と表すことができます。

この式より、与えられた式の最小値は \(\displaystyle \left\lfloor\frac{|C|+1}2\right\rfloor\) であり、その値は奇数番目の \(1\) の右隣に \(1\) が存在するように並べることでのみ得られることが分かります。（ただし、\(|C|\) が奇数の場合は \(A_N=1\) とする）

この事実を元に、元の問題を考えます。

\(\displaystyle \sum_{i=1}^N\bigoplus_{1\le j\le i}P_j\) の値を \(P\) の スコア と呼びます。

まず bit 毎に考えることで \(P\) のスコアの下界を導出します。

\(1\) 以上 \(N\) 以下の整数で二進数で表した時 \(2^k\) の位が \(1\) であるようなものの個数を \(X_k\) とします。上の議論より、bit 毎に上の問題を独立に解くことでスコアの下界として \(\displaystyle \sum_k 2^k\times \left\lfloor \frac{X_k+1}2\right\rfloor\) が得られます。

そして、多くの場合にこの下界は達成可能です。具体的には、以下のような手順で条件を満たす \(P\) を構成可能です：

• \(P=(1,2,\ldots,N)\) とする。
• \(\displaystyle k=0,1,\ldots,\left\lfloor\frac{N-3}4 \right\rfloor\) に対して、\(P_{4k+2}\) と \(P_{4k+3}\) を swap する。

以上の手順で \(N\equiv 0,1,3\bmod 4\) の場合はスコアの下界が達成可能です。

構成方法より \(P_0=0\) として \(P_{4k},P_{4k+1},P_{4k+2},P_{4k+3}\) の \(k\geq 2\) に対する \(2^k\) の位は全て同じです。また、\(k=0,1\) に対しても \(N\bmod 4\) の値で場合分けして考えることで \(N\equiv 0,1,3 \bmod 4\) の場合に下界を達成していることが確認できます。

\(N\equiv 2\bmod 4\) の場合を考えます。ある順列 \(P\) が上で導出したスコアの下界を達成したと仮定します。このとき、\(k=1,2,\ldots\) に対し \(1\) 以上 \(N-1\) のうち \(2^k\) の位が \(1\) である整数は偶数個であるため、\(P_N=N\) である必要があります。しかし、\(N\) が偶数であることに加え \(1\) 以上 \(N-1\) のうち \(2^0\) の位が \(1\) である整数は奇数個であるため \(P\) がスコアの下界を達成していることに矛盾します。以上より、\(N\equiv 2\bmod 4\) の場合にはスコアの下界を達成することはできません。

しかし、スコアの下界に \(1\) 足した値は上の構成方法で達成可能です。以上より、上の手順で全ての \(N\) に対しスコアの最小値が達成可能であることが分かります。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(N)\) です。

実装例(Python3)

for _ in range(int(input())):
    n = int(input())
    p = [i + 1 for i in range(n)]
    for i in range(2, n, 4):
        p[i - 1], p[i] = p[i], p[i - 1]
    print(*p)

原案：sounansya