B. Найти массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$[a_1, a_2, \dots, a_n]$$$ такой, что $$$1 \le a_i \le 10^9$$$. Пусть $$$S$$$ – сумма всех элементов массива $$$a$$$.

Назовем массив $$$b$$$, состоящий из $$$n$$$ целых чисел красивым, если:

  • $$$1 \le b_i \le 10^9$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$;
  • для каждой пары соседних целых чисел из массива $$$(b_i, b_{i + 1})$$$, либо $$$b_i$$$ делит $$$b_{i + 1}$$$, либо $$$b_{i + 1}$$$ делит $$$b_i$$$ (или оба числа делятся друг на друга);
  • $$$2 \sum \limits_{i = 1}^{n} |a_i - b_i| \le S$$$.

Ваша задача — найти красивый массив. Можно показать, что по крайней мере один красивый массив всегда существует.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк. Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 50$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Для каждого набора входных данных выведите красивый массив $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) на отдельной строке. Можно показать, что существует по крайней мере один красивый массив. Если ответов несколько, выведите любой из них.

Пример
Входные данные
4
5
1 2 3 4 5
2
4 6
2
1 1000000000
6
3 4 8 1 2 3
Выходные данные
3 3 3 3 3
3 6
1 1000000000
4 4 8 1 3 3