Observe the Patterns,

Your assumptions might DO.

But, what will be your approach,

When there will be no CLUE...?

---    XUDOKU

XOXO_Bunnyface is learning Bit masking. While watching the tutorials on Bit masking with his friend George Boole, an idea came upon the mind of George. As being the inventor of the Boolean algebra, George Boole invented a game to trick XOXO, who always prefer assumptions than proof.

George named the game as XUDOKU. The game consists of a 3 * N matrices. Where 3 is the constant number of rows and N is the number of columns. Initially the first row is filled with N integers. To win the tricky game, XOXO has to fill the remaining two rows with some integers in such a way that, the following conditions are true.

1. X_{(3, i)} = X_{(1, i)} ⊕ X_{(2, i)}; for all i (1 <= i <= N).
2. X_{(3, i)} = X_{(3, i + 1)} & X_{(3, i)}; for all i (1 <= i <= N - 1).
3. The number sequence of the 2^nd row should be lexicographically smallest.
4. The number sequence of the 3^rd row should be non-decreasing.

(X_{(i, j)} means the j-th element of the i-th row of the XUDOKU matrices).

Input

The first line contains G (1 <= G <= 1000), the number of games to be played.

The second line contains N (2 <= N <= 2*10⁵), the width of the XUDOKU board. I.e. number of columns.

The Third line contains N integers of the First row. X_{(1, j)} (0 <= X_{(1, j)} < 2³⁰)

Output

For each G, you have to print the output in the following manner.

Game #G_i

X_{(1, i)} X_{(1, i + 1)} X_{(1, i + 2)} X_{(1, i + 3)} X_{(1, i + 4)} ... X_{(1, N)}

X_{(2, i)} X_{(2, i + 1)} X_{(2, i + 2)} X_{(2, i + 3)} X_{(2, i + 4)} ... X_{(2, N)}

X_{(3, i)} X_{(3, i + 1)} X_{(3, i + 2)} X_{(3, i + 3)} X_{(3, i + 4)} ... X_{(3, N)}

Samples

Input:
3
4
9 3 7 13
8
18 6 3 2 4 0 0 4
4
16 18 17 14

Output:
Game #1
9 3 7 13
0 8 8 2
9 11 15 15
Game #2
18 6 3 2 4 0 0 4
0 16 20 21 19 23 23 19
18 22 23 23 23 23 23 23
Game #3
16 18 17 14
0 0 2 17
16 18 19 31