题目描述

给定一个长度为 $n$ 的正整数数组 $a_1, a_2, \ldots, a_n$。每次操作，你可以选择数组中的任意一个数，将其加 $1$。

请在最多进行 $2n$ 次操作后，使得数组满足以下性质：对于每个 $i=1,2,\ldots,n-1$，$a_{i+1}$ 不能被 $a_i$ 整除。

你不需要最小化操作次数。

输入格式

每个测试点包含多组测试用例。第一行包含测试用例个数 $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$。

可以证明，在给定的限制下总能找到一个满足条件的答案。如果有多种答案，输出任意一种均可。

说明/提示

在第一个测试用例中，数组 $[4, 5, 6, 7]$ 可以通过对第一个元素操作 $2$ 次，对第二个元素操作 $1$ 次，对第三个元素操作 $3$ 次，对最后一个元素操作 $1$ 次得到。总共进行了 $7$ 次操作，小于本例允许的 $8$ 次操作。

在第二个测试用例中，数组 $[3, 2, 3]$ 可以通过对第一个元素操作两次得到。另一种可能的结果是 $[2, 3, 5]$，因为不需要最小化操作次数。

在第三个测试用例中，不进行任何操作即可得到满足条件的数组。注意，不一定要进行操作。

由 ChatGPT 4.1 翻译

样例

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

4 5 6 7
3 2 3
4 2