## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] ANDfinity Codeforces Solution | Codeforces Problem Solution 2022

E. ANDfinity
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bit Lightyear, to the ANDfinity and beyond!

After graduating from computer sciences, Vlad has been awarded an array ${a}_{1},{a}_{2},\dots ,{a}_{n}$ of $n$ non-negative integers. As it is natural, he wanted to construct a graph consisting of $n$ vertices, numbered $1,2,\dots ,n$. He decided to add an edge between $i$ and $j$ if and only if ${a}_{i}\mathrm{&}{a}_{j}>0$, where $\mathrm{&}$ 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}>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?

Input
There are several test cases in the input data. The first line contains a single integer $t$ ($1\le t\le 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\le n\le 2000$).
The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($0\le {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.