Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
C1. Disgusting + GCD (Constructive Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the constructive version of the problem.

In this version, you are kijjot.

An array $$$b$$$ is called disgusting if there exist indices $$$i \lt j$$$ such that $$$1 \lt \gcd(b_i, b_j) \lt \min(b_i, b_j)$$$$$$^{\text{∗}}$$$.

You are given an array $$$a$$$ of length $$$n$$$, consisting of positive integers. To prevent eternal merging, you need to make it not disgusting.

To do this, you can perform the following operation: choose an index $$$1 \le i \le n$$$ and a positive integer $$$1 \le x \le 10^9$$$ such that $$$\gcd(a_i, x) = 1$$$, and increase $$$a_i$$$ by $$$x$$$. Note that the condition is checked using the current value of $$$a_i$$$ before the operation, not its value in the original array.

Your strength is running low, so you can perform operations subject to the following restrictions:

  • You can perform at most $$$n + 10$$$ operations.
  • The sum of the values of $$$x$$$ over all performed operations must not exceed the sum of the elements of the original array $$$a$$$.

Find any valid array obtained as a result of applying the operations. It can be shown that under the given constraints, such an array always exists.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \le a_i \le 10^5$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$a_i \le b_i \le 10^9$$$) — the array $$$b$$$ resulting from the operations.

The array $$$b$$$ must not be disgusting and must be obtainable from $$$a$$$ using the allowed operations while satisfying both restrictions. If there are multiple valid arrays, output any of them.

Example
Input
3
2
7 12
3
7 9 12
7
8 76 49 26 24 80 99
Output
7 12
7 25 12
9 77 50 27 25 81 100
Note

In the first example, we can perform no operations, since the array is already not disgusting.

In the second example, the array is disgusting because $$$1 \lt \gcd(a_2, a_3) = \gcd(9, 12) = 3 \lt \min(a_2, a_3) = \min(9, 12) = 9$$$ holds. We can choose $$$i=2$$$ and $$$x=16$$$, since $$$\gcd(x, a_i) = \gcd(16, 9) = 1$$$. After this, the array $$$a$$$ will become equal to $$$[7, 25, 12]$$$ and will no longer be disgusting.