You are given an array $$A$$ consisting of $$N$$ positive integers. Your task is to find an array $$B$$ of length $$N$$ satisfying the following conditions:

• $$ B_i > 0$$ for all $$ 1 \leq i \leq N $$
• $$B_i \leq B_{i+1}$$, for all $$ 1 \leq i < N$$
• $$B_i$$ is divisible by $$A_i$$ for all $$ 1 \leq i \leq N$$
• $$\sum\limits_{i=1}^{N} B_i$$ is minimum

You are given $$T$$ test cases.

Input format

• The first line contains a single integer $$T$$ denoting the number of test cases.
• The first line of each test case contains a single integer $$N$$ denoting the length of the array.
• The second line of each test case contains $$N$$ space-separated integers denoting the integer array $$A$$.

Output format

For each test case (in a separate line), print $$N$$ space-separated integers denoting $$B_1, B_2, .. , B_N$$. If there are multiple answers, you can print any of them. It is guaranteed that under the given constraints at least 1 $$B$$ exists.

Constraints

$$ 1 \le T \le 1000 \\
1 \le N \le 2.5 \times 10^5 \\
1 \le A_i \le 10^9 \\
\text{Sum of N over all test cases does not exceed } 7.5 \times 10^5 $$