Problem Description

Given a sequence $a$ consists $n$ distinct integers. Please construct a permutation $p$ and a sequence $b$ satisfied:

- Both $p$ and $b$ have exactly $n$ elements;
- For every $i \in [2,n]$ ,there exist an indice $j(1 \leq j \leq i-1)$ such that $b_i \oplus p_j=0$.

You need to minimize $\sum\limits_{i=2}^n popcount(a[p[i]] \oplus a[b[i]])$, where $popcount(x)$ represents the number of $1$ in the binary representation of $x$, $\oplus$ means bitwise exclusive OR operation.

Input

The input consists of multiple test cases. The first line contains an integer $T$ $(1 \leq T \leq 10)$ — the number of test cases.
The description of the test cases follows.

The first line contains one integers $n$ $(1 \leq n \leq 2*10^5)$ .

The second line contains $n$ distinct integers $a_1,a_2,\dots,a_n(0 \leq a_i < 2^{18})$ .

Output

For each test case, print three lines.

The first line contains one number, represents the minimum value.

The second line contains $n$ numbers $p_1,p_2,\dots,p_n$ — the permutation you construct.

The last line contains $n$ numbers $b_1,b_2,\dots,b_n$ — the sequence you construct.

If there are several answers, you can print any.

2
3
2 3 4
4
65 23 11 43

3
1 2 3 
3 1 1 
7
1 3 4 2 
4 1 3 3