Non Comprime Neighbours solution codechef- An array B of length N (N≥2) is said to be good if the following conditions hold: For all 1≤i≤N, 2≤Bi≤106 gcd(Bi−1,Bi)≠1 for all i (2≤i≤N)

An array BB of length NN (N2)(N≥2) is said to be good if the following conditions hold:

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

You have an array AA of length NN (2Ai1052≤Ai≤105). You want to make the array AA good.

To do so, you can change atmost 2N3⌈2⋅N3⌉ elements of AA.

Print the final array after changing AA to a good array. If there are multiple possible final arrays, print any of them.

It is guaranteed that AA can be made good after changing atmost 2N3⌈2⋅N3⌉ elements of AA.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follow.
  • The first line of each test case contains an integer NN – the length of the array.
  • The second line of each test case contains NN space-separated integers A1,A2,...,ANA1,A2,…,AN representing the initial array AA.

Output Format

For each test case, output a single line containing NN space-separated integers, denoting the elements of the final array after converting AA to a good array. The ii-th of these NN integers is ii-th element in the final array.

If multiple arrays exist which satisfy the conditions, print any of them.

Note: Final array should differ from original array at atmost 2N3⌈2⋅N3⌉indices.

Constraints

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

Sample Input 1 

2
3
6 12 5
3
5 5 5

Sample Output 1 

6 12 8
5 5 5

Explanation

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

Test Case 2: Array AA is already good.

  1. For Solution

    Click Here!

Leave a Comment

Your email address will not be published.