Non Comprime Neighbours solution codechef

For Solution

Click Here!

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

• For all 1≤i≤N1≤i≤N, 2≤Bi≤1062≤Bi≤106
• gcd(Bi−1,Bi)≠1gcd(Bi−1,Bi)≠1 for all ii (2≤i≤N)(2≤i≤N).

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

To take action, you may change atmost ⌈2⋅N3⌉⌈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 ⌈2⋅N3⌉⌈2⋅N3⌉ parts of AA.

Enter Format

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 ⌈2⋅N3⌉⌈2⋅N3⌉indices.

Constraints

Non Comprime Neighbours solution codechef

• 1≤T≤1051≤T≤105
• 2≤N≤1052≤N≤105
• 2≤Ai≤1052≤Ai≤105
• Sum of NN doesn’t exceed 2⋅1052⋅105 over all testcases

Pattern Enter 1 

2
3
6 12 5
3
5 5 5

Pattern Output 1

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 ≤⌈2⋅N3⌉≤⌈2⋅N3⌉.

Check Case 2: Array AA is already good.

For Solution

Click Here!