Alya has been given a hard problem. Unfortunately, she is too busy running for student council. Please solve this problem for her.

Given an integer $$$n$$$, construct a permutation $$$p$$$ of integers $$$1, 2, \ldots, n$$$ that maximizes the value of $$$k$$$ (which is initially $$$0$$$) after the following process.

Perform $$$n$$$ operations, on the $$$i$$$-th operation ($$$i=1, 2, \dots, n$$$),

If $$$i$$$ is odd, $$$k=k\,\&\,p_i$$$, where $$$\&$$$ denotes the bitwise AND operation.
If $$$i$$$ is even, $$$k=k\,|\,p_i$$$, where $$$|$$$ denotes the bitwise OR operation.

Input

The first line contains a single integer $$$t$$$ ($$$1\le t\le 500$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$5\le n\le 2 \cdot 10^5$$$) — the length of the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the maximum value of $$$k$$$ in the first line and output the permutation $$$p_1, p_2,\ldots, p_n$$$ in the second line.

If there are multiple such permutations, output any.

Note

For the first test case, the value of $$$k$$$ is determined as follows:

$$$k = 0$$$ initially.

On the $$$1$$$st operation, $$$1$$$ is odd, so Alya sets $$$k$$$ to be $$$k\&p_1 = 0\&2 = 0$$$.
On the $$$2$$$nd operation, $$$2$$$ is even, so Alya sets $$$k$$$ to be $$$k|p_2 = 0|1 = 1$$$.
On the $$$3$$$rd operation, $$$3$$$ is odd, so Alya sets $$$k$$$ to be $$$k\&p_3 = 1\&3 = 1$$$.
On the $$$4$$$th operation, $$$4$$$ is even, so Alya sets $$$k$$$ to be $$$k|p_4 = 1|4 = 5$$$.
On the $$$5$$$th operation, $$$5$$$ is odd, so Alya sets $$$k$$$ to be $$$k\&p_5 = 5\&5 = 5$$$.

The final value of $$$k$$$ is $$$5$$$. It can be shown that the final value of $$$k$$$ is at most $$$5$$$ for all permutations of length $$$5$$$. Another valid output is $$$[2, 3, 1, 4, 5]$$$.

For the second test case, the final value of $$$k$$$ is $$$7$$$. It can be shown that the final value of $$$k$$$ is at most $$$7$$$ for all permutations of length $$$6$$$. Other valid outputs include $$$[2, 4, 1, 6, 3, 5]$$$ and $$$[5, 2, 6, 1, 3, 4]$$$.

Alya and Permutation

Examples