XOR Triples

Time limit5sMemory limit256 MB

Summary

Choose the largest subset of 1 to N with no three distinct values xoring to zero, breaking ties by smallest lexicographic order.

Level: Medium5 of 10
Topics: Brute force, Bit manipulation
Solved: No attempts yet

Problem

Choose distinct integers from 1 to $N$ and collect them into one sequence. For every choice of three distinct chosen numbers $a$ , $b$ , $c$ , the value $a \oplus b \oplus c$ must not be 0, where $\oplus$ is the bitwise exclusive or (XOR).

Find a sequence of maximum length that satisfies this condition.

Input

The first line contains the number of test cases $T$ ( $1 \leq T \leq 100$ ).

Each of the next $T$ lines contains one integer $N$ ( $1 \leq N \leq 20$ ).

Output

Print the answer for each test case on two lines.

The first line holds the length of the sequence.
The second line holds the sequence sorted in increasing order, separated by single spaces.

If several sequences reach the maximum length, print only the one that is lexicographically smallest after sorting in increasing order.

Examples2

Example 1
Input
```
2
2
3
```
Expected output
```
2
1 2
2
1 2
```
Example 2
Input
```
1
1
```
Expected output
```
1
1
```