# For Solution

An array BB of size NN (N2)(N≥2) is alleged to be good if the next situations maintain:

• For all 1iN1≤i≤N2Bi1062≤Bi≤106
• gcd(Bi1,Bi)1gcd(Bi−1,Bi)≠1 for all ii (2iN)(2≤i≤N).

You might have an array AA of size NN (2Ai1052≤Ai≤105). You wish to make the array AA good.

To take action, you may change atmost 2N3⌈2⋅N3⌉ parts of AA.

Print the ultimate array after altering AA to a great array. If there are a number of doable closing arrays, print any of them.

It’s assured that AA may be made good after altering atmost 2N3⌈2⋅N3⌉ parts of AA.

## Non Comprime Neighbours solution codechef

• The primary line of enter accommodates a single integer TT, denoting the variety of take a look at circumstances. The outline of TT take a look at circumstances observe.
• The primary line of every take a look at case accommodates an integer NN – the size of the array.
• The second line of every take a look at case accommodates NN space-separated integers A1,A2,...,ANA1,A2,…,AN representing the preliminary array AA.

### Output Format

For every take a look at case, output a single line containing NN space-separated integers, denoting the weather of the ultimate array after changing AA to a great array. The ii-th of those NN integers is ii-th factor within the closing array.

If a number of arrays exist which fulfill the situations, print any of them.

Be aware: Remaining array ought to differ from authentic array at atmost 2N3⌈2⋅N3⌉indices.

## Non Comprime Neighbours solution codechef

• 1T1051≤T≤105
• 2N1052≤N≤105
• 2Ai1052≤Ai≤105
• Sum of NN doesn’t exceed 21052⋅105 over all testcases

### Pattern Enter 1

2
3
6 12 5
3
5 5 5


## Non Comprime Neighbours solution codechef

6 12 8
5 5 5


### Clarification

Check Case 1: We will change A3A3 to 88. Now, AA is sweet since gcd(A1,A2)=6gcd(A1,A2)=6 and gcd(A2,A3)=4gcd(A2,A3)=4. Therefore, we made AA good after making solely 11 change which is 2N3≤⌈2⋅N3⌉.

Check Case 2: Array AA is already good.