E. Rama's Birthday
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad gave Rama the most basic birthday gift, an array $$$a$$$ of $$$n$$$ integers on a piece of paper. Unfortunately, Rama's new cat ripped it apart.

Bagheera

Luckily, she remembers an array $$$b$$$ of $$$n$$$ integers such that $$$b_i = gcd(a_1, a_2, \ldots, a_i)$$$, now she wants you to construct an array $$$a$$$ that satisfies the array $$$b$$$.

Ahmad is considerate and loves cats, so he will accept any valid array $$$a$$$.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 2\cdot10^5)$$$ – the number of integers in $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \leq 10^9)$$$ – the array she remembers.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, if there's no valid array that satisfies $$$b$$$ print -1, otherwise print $$$n$$$ integers the array $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$. If there are multiple solutions print any.

Example
Input
3
4
16 8 2 2
4
30 15 5 1
4
3 4 2 1
Output
16 24 10 2 
30 15 25 13 
-1