Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

C1. Омерзительно + GCD (конструктивная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это конструктивная версия задачи.

В этой версии вы kijjot.

Массив $$$b$$$ назовём омерзительным, если существуют индексы $$$i \lt j$$$ такие, что $$$1 \lt \gcd(b_i, b_j) \lt \min(b_i, b_j)$$$$$$^{\text{∗}}$$$.

Вам дан массив $$$a$$$ длины $$$n$$$, состоящий из положительных целых чисел. Для предотвращения вечного слияния вам необходимо сделать его не омерзительным.

Для этого вы можете выполнять следующую операцию: выбрать индекс $$$1 \le i \le n$$$ и положительное целое число $$$1 \le x \le 10^9$$$ такие, что $$$\gcd(a_i, x) = 1$$$, и увеличить $$$a_i$$$ на $$$x$$$. Обратите внимание, что условие проверяется для текущего значения $$$a_i$$$ перед выполнением операции, а не для его значения в исходном массиве.

Ваши силы на исходе, поэтому вы можете выполнять операции со следующими ограничениями:

  • Вы можете выполнить не более $$$n + 10$$$ операций.
  • Сумма значений $$$x$$$ по всем выполненным операциям не должна превышать сумму элементов исходного массива $$$a$$$.

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

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \le a_i \le 10^5$$$) — элементы массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$a_i \le b_i \le 10^9$$$) — массив $$$b$$$, получившийся в результате выполнения операций.

Массив $$$b$$$ не должен быть омерзительным и должен быть получен из $$$a$$$ с помощью разрешённых операций с соблюдением обоих ограничений. Если существует несколько подходящих массивов, выведите любой из них.

Пример
Входные данные
3
2
7 12
3
7 9 12
7
8 76 49 26 24 80 99
Выходные данные
7 12
7 25 12
9 77 50 27 25 81 100
Примечание

В первом примере мы можем не использовать ни одной операции, поскольку массив уже не является омерзительным.

Во втором примере массив является омерзительным, поскольку выполняется $$$1 \lt \gcd(a_2, a_3) = \gcd(9, 12) = 3 \lt \min(a_2, a_3) = \min(9, 12) = 9$$$. Мы можем выбрать $$$i=2$$$ и $$$x=16$$$, так как $$$\gcd(x, a_i) = \gcd(16, 9) = 1$$$. После этого массив $$$a$$$ станет равен $$$[7, 25, 12]$$$ и перестанет быть омерзительным.