CF1689E.ANDfinity

Bit Lightyear, to the ANDfinity and beyond!

After graduating from computer sciences, Vlad has been awarded an array $a_1,a_2,\ldots,a_n$ of $n$ non-negative integers. As it is natural, he wanted to construct a graph consisting of $n$ vertices, numbered $1, 2,\ldots, n$. He decided to add an edge between $i$ and $j$ if and only if $a_i \& a_j \gt 0$, where $\&$ denotes the bitwise AND operation.

Vlad also wants the graph to be connected, which might not be the case initially. In order to satisfy that, he can do the following two types of operations on the array:

1. Choose some element $a_i$ and increment it by $1$.
2. Choose some element $a_i$ and decrement it by $1$ (possible only if $a_i \gt 0$).

It can be proven that there exists a finite sequence of operations such that the graph will be connected. So, can you please help Vlad find the minimum possible number of operations to do that and also provide the way how to do that?

比特·光年，向与无穷（ANDfinity）进发，超越一切！

在计算机科学专业毕业后，弗拉德获得了一个由 $n$ 个非负整数组成的数组 $a_1,a_2,\ldots,a_n$。按照惯例，他希望构造一个包含 $n$ 个顶点的图，顶点编号为 $1, 2,\ldots, n$。他决定：当且仅当 $a_i \& a_j \gt 0$ 时，在顶点 $i$ 和 $j$ 之间添加一条边，其中 $\&$ 表示按位与运算。

弗拉德还希望该图是连通的，但初始状态下图未必满足这一性质。为了使其连通，他可以在数组上执行以下两类操作：

1. 选择某个元素 $a_i$，将其加 $1$；
2. 选择某个元素 $a_i$，将其减 $1$（仅当 $a_i \gt 0$ 时允许执行）。

可以证明：总存在一个有限长度的操作序列，使得最终得到的图是连通的。那么，你能否帮弗拉德找出使图连通所需的最少操作次数，并同时给出一种具体的操作方案？

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 \lt 2^{30}$) — the elements of the array.

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

输入数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\leq n \leq 2000$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\leq a_i \lt 2^{30}$），表示数组的元素。

保证所有测试用例的 $n$ 值之和不超过 $2000$。

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.

对于每个测试用例，在第一行输出一个整数 $m$ —— 所需的最少操作次数。在第二行输出经过一系列有效操作后的数组，使得题目中所述的图变为连通图。

若存在多种解法，输出任意一种即可。

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 \gt 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 \gt 0$ hence the graph is connected. One operation has to be done since the graph is not connected at the beginning.

在第一个测试用例中，图已经是连通的。

在第二个测试用例中，我们可以将 $0$ 增加两次，最终得到数组 $[2,2]$。由于 $2 \& 2 = 2 \gt 0$，该图是连通的。可以证明，仅执行一次操作是不够的。

在第三个测试用例中，我们可以将 $12$ 减少一次，最终得到数组 $[3,11]$。由于 $3 \& 11 = 3 \gt 0$，该图是连通的。由于图在初始状态下不连通，因此必须执行一次操作。