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

Вам дан массив из $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$. За одну операцию вы можете выбрать любой элемент массива и увеличить его на $$$1$$$.

Выполните не более $$$2n$$$ операций, чтобы массив удовлетворял следующему свойству: $$$a_{i+1}$$$ не делится на $$$a_i$$$ для каждого $$$i = 1, 2, \ldots, n-1$$$.

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

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq 10^9$$$) — заданный массив.

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

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

Для каждого теста выведите ответ на отдельной строке.

В единственной строке выведите $$$n$$$ целых чисел — итоговый массив $$$a$$$ после применения не более чем $$$2n$$$ операций.

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

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

В первом наборе входных данных массив $$$[4, 5, 6, 7]$$$ может быть получен путем применения $$$2$$$ операций к первому элементу, $$$1$$$ операции ко второму элементу, $$$3$$$ операций к третьему элементу и $$$1$$$ операции к четвертому элементу. Общее количество выполненных операций составляет $$$7$$$, что меньше разрешенных $$$8$$$ операций в данном случае.

Во втором наборе входных данных массив $$$[3, 2, 3]$$$ можно получить, применив две операции к первому элементу. Другой возможный результирующий массив может быть $$$[2, 3, 5]$$$, потому что общее количество операций не обязано быть минимальным.

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