CF1737F.Ela and Prime GCD

After a long, tough, but fruitful day at DTL, Ela goes home happily. She entertains herself by solving Competitive Programming problems. She prefers short statements, because she already read too many long papers and documentation at work. The problem of the day reads:

You are given an integer $c$. Suppose that $c$ has $n$ divisors. You have to find a sequence with $n - 1$ integers $[a_1, a_2, ... a_{n - 1}]$, 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 \lt n - 1$, $\gcd(a_i, a_{i + 1})$ 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(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$ and a prime number is a positive integer which has exactly $2$ divisors.

在 DTL 经历了漫长、艰辛但富有成果的一天后，Ela 心情愉快地回到了家。她通过解决竞赛编程题目来娱乐自己。她偏爱简短的题面，因为在工作中她已经阅读了太多冗长的论文和文档。当天的题目如下：

给定一个整数 $c$。假设 $c$ 有 $n$ 个正因数。你需要构造一个包含 $n - 1$ 个整数的序列 $[a_1, a_2, \dots, a_{n - 1}]$，满足以下条件：

• 每个元素严格大于 $1$；
• 每个元素均为 $c$ 的正因数；
• 所有元素互不相同；
• 对所有 $1 \le i < n - 1$，$\gcd(a_i, a_{i + 1})$ 是一个质数。

本题中，由于 $c$ 可能过大，因此直接给出其质因数分解结果。注意：$\gcd(x, y)$ 表示整数 $x$ 与 $y$ 的最大公约数（GCD），而质数是指恰好有 $2$ 个正因数的正整数。

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, \ldots, b_m$ ($1 \le b_i \lt 2^{20}$) — exponents of corresponding prime factors of $c$, so that $c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m}$ and $n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1)$ hold. $p_i$ is the $i$-th smallest prime number.

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $m$（$1 \le m \le 16$）——$c$ 的质因数个数。

每个测试用例的第二行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$1 \le b_i \lt 2^{20}$）——分别对应 $c$ 的各质因数的指数，使得 $c = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_m^{b_m}$ 且 $n = (b_1 + 1)(b_2 + 1) \ldots (b_m + 1)$ 成立。其中 $p_i$ 表示第 $i$ 个最小的质数。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $2^{20}$。

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.

对每个测试用例，输出一行答案。若不存在满足给定 $c$ 的序列，则输出 $-1$。

否则，输出 $n - 1$ 行。在第 $i$ 行中，输出 $m$ 个以空格分隔的整数；其中第 $j$ 个整数等于 $a_i$ 中第 $j$ 个质数的指数。

若存在多个合法答案，输出任意一个即可。

In each test case, the values of $c$ are $6$, $2$, $30$, $16$, and $12$ in that order.

In the first test case, $1$, $2$, $3$, $6$ are divisors of $6$. Here, sequences $[2, 6, 3]$ and $[3, 6, 2]$ can be answer. Permutation $[3, 2, 6]$ is invalid because $\gcd(a_1, a_2) = 1$ is not a prime number.

In the forth test case, $1$, $2$, $4$, $8$, $16$ are divisors of $16$. Among the permutation of sequence $[2, 4, 8, 16]$, no valid answer exist.

每个测试用例中，$c$ 的值依次为 $6$、$2$、$30$、$16$ 和 $12$。

在第一个测试用例中，$1$、$2$、$3$、$6$ 是 $6$ 的约数。此时，序列 $[2, 6, 3]$ 和 $[3, 6, 2]$ 均可作为答案。排列 $[3, 2, 6]$ 无效，因为 $\gcd(a_1, a_2) = 1$ 不是质数。

在第四个测试用例中，$1$、$2$、$4$、$8$、$16$ 是 $16$ 的约数。在序列 $[2, 4, 8, 16]$ 的所有排列中，不存在合法答案。