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

• 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 have an array AA of length NN (2≤Ai≤1052≤Ai≤105). You want to make the array AA good.

To do so, you can change atmost ⌈2⋅N3⌉⌈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 ⌈2⋅N3⌉⌈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 ⌈2⋅N3⌉⌈2⋅N3⌉indices.

Constraints

• 1≤T≤1051≤T≤105
• 2≤N≤1052≤N≤105
• 2≤Ai≤1052≤Ai≤105
• Sum of NN does not exceed 2⋅1052⋅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 ≤⌈2⋅N3⌉≤⌈2⋅N3⌉.

Test Case 2: Array AA is already good.

1. For Solution

   Click Here!