Migrated from Lutece 1302 Good Water Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given $n$ integers, you are allowed to change the numbers in a sequence of steps.

In each step, you can:

Select two numbers $x$ and $y$.

Erase $x$ and $y$.

Write two new integers onto the blackboard: $gcd(x, y)$ and $lcm(x, y)$.

(Above, $gcd(x,y)$ denotes the greatest common divisor and $lcm(x,y)$ the least common multiple of $x$ and $y$.)

Your goal is to maximize the maximum number. Under that circumstance, try to maximize the second largest number, the third largest number, and so on.

Input

The first line contains an integer $T$, denoting the number of the test cases.

$T \le 5$

For each case, there is an integer $n$. $(n \le 10^5)$

The next line contains $n$ integers. Let $a_i$ denotes the $i^{th}$ number. $(a_i \le 10^6)$

Output

Output $n$ numbers, the answer mod $10^9+7$, denoting the largest number, the second largest number, and so on.

Samples

1
4
999983 999983 999979 32

783787438 999983 1 1

Resources

The 14th UESTC Programming Contest Preliminary