E. Бесконечность
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После окончания университета Влад получил массив $$$a_1,a_2,\ldots,a_n$$$ из $$$n$$$ целых неотрицательных чисел. Он сразу же захотел построить граф, состоящий из $$$n$$$ вершин, пронумерованных $$$1, 2,\ldots, n$$$. Он решил добавлять ребро между $$$i$$$ и $$$j$$$ тогда и только тогда, когда $$$a_i \& a_j > 0$$$, где $$$\&$$$ обозначает операцию побитового И.

Влад также хочет, чтобы такой граф был связным, что, к сожалению, может быть не так. Чтобы удовлетворить свое желание, он может выполнять следующие два типа операций над массивом:

  • Выбрать некоторый элемент $$$a_i$$$ и увеличить его на $$$1$$$.
  • Выбрать некоторый элемент $$$a_i$$$ и уменьшить его на $$$1$$$ (разрешено, только если $$$a_i > 0$$$).

Можно доказать, что существует конечная последовательность таких операций, при которой граф станет связным. Не могли бы вы помочь Владу найти минимально возможное количество операций для этого, а также предоставить способ, как это сделать?

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2\leq n \leq 2000$$$).

Во второй строке каждого набора задано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i < 2^{30}$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2000$$$.

Выходные данные

Для каждого набора входных данных выведите в первой строке единственное целое число $$$m$$$  — минимальное количество операций. Во второй строке выведите массив после допустимой последовательности операций, которые были выполнены так, что граф из задачи стал связным.

Если решений несколько, выведите любое.

Пример
Входные данные
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
Примечание

В первом наборе входных данных граф уже связен.

Во втором наборе входных данных мы можем дважды увеличить $$$0$$$ и получить массив $$$[2,2]$$$. Поскольку $$$2 \& 2 = 2 > 0$$$, граф связен. Можно показать, что одной операции недостаточно.

В третьем наборе входных данных мы можем один раз уменьшить $$$12$$$ и получить массив $$$[3,11]$$$. $$$3 \& 11 = 3 > 0$$$, следовательно, граф связен. Необходимо выполнить одну операцию, так как граф вначале не связен.