## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Ela and Prime GCD Codeforces Solution

F. Ela and Prime GCD
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an integer

$c$. Suppose that $c$ has $n$ divisors. You have to find a sequence with $n-1$ integers $\left[{a}_{1},{a}_{2},...{a}_{n-1}\right]$, which satisfies the following conditions:

• Each element is strictly greater than $1$.
• Each element is a divisor of $c$.
• All elements are distinct.
• For all $1\le i$gcd\left({a}_{i},{a}_{i+1}\right)$ is a prime number.

In this problem, because $c$ can be too big, the result of prime factorization of $c$ is given instead. Note that $gcd\left(x,y\right)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$ and a prime number is a positive integer which has exactly $2$ divisors.

Input

The first line contains one integer $t$ ($1\le t\le {10}^{4}$) - the number of test cases.

The first line of each test case contains one integer $m$ ($1\le m\le 16$) - the number of prime factor of $c$.

The second line of each test case contains $m$ integers ${b}_{1},{b}_{2},\dots ,{b}_{m}$ ($1\le {b}_{i}<{2}^{20}$) — exponents of corresponding prime factors of $c$, so that $c={p}_{1}^{{b}_{1}}\cdot {p}_{2}^{{b}_{2}}\cdot \dots \cdot {p}_{m}^{{b}_{m}}$ and $n=\left({b}_{1}+1\right)\left({b}_{2}+1\right)\dots \left({b}_{m}+1\right)$ hold. ${p}_{i}$ is the $i$-th smallest prime number.

Solution Click Below:-  👉
👇👇👇👇👇

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed ${2}^{20}$.

Output

Print the answer for each test case, one per line. If there is no sequence for the given $c$, print $-1$.

Otherwise, print $n-1$ lines. In $i$-th line, print $m$ space-separated integers. The $j$-th integer of $i$-th line is equal to the exponent of $j$-th prime number from ${a}_{i}$.

If there are multiple answers, print any of them.