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$