Description

Input

There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains an integer $n$ ($2\leq n \leq 2000$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0\leq a_i < 2^{30}$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

Output

For each test case, print a single integer $m$ in the first line — the minimum number of operations. In the second line print the array after a valid sequence of operations that have been done such that the graph from the task becomes connected.

If there are multiple solutions, output any.

4
5
1 2 3 4 5
2
0 2
2
3 12
4
3 0 0 0

0
1 2 3 4 5
2
2 2
1
3 11
3
3 1 1 1

Note

In the first test case, the graph is already connected.

In the second test case, we can increment $0$ twice and end up with the array $[2,2]$. Since $2 \& 2 = 2 > 0$, the graph is connected. It can be shown that one operation is not enough.

In the third test case, we can decrement $12$ once and we end up with an array $[3,11]$. $3 \& 11 = 3 > 0$ hence the graph is connected. One operation has to be done since the graph is not connected at the beginning.