← 返回题目列表

Codeforces · 1794/B

B. 不除

中文机器翻译题面 查看原题

给定一个由 $$$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$$$ 整数 - 应用最多 $$$2n$$$ 操作后得到的数组 $$$a$$$。

我们可以证明在给定的约束下答案总是存在。如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
4
2 4 3 6
3
1 2 3
2
4 2

输出 #1

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]$$$,因为操作总数不需要是最小值。

在第三个测试用例中,不应用任何操作会产生满足语句属性的数组。请注意,并非强制执行操作。