[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 𝑛−1$n-1$ integers [𝑎1,𝑎2,...𝑎𝑛−1]$[a_1,a_2,...a_{n-1}]$, which satisfies the following conditions:

• Each element is strictly greater than 1$1$.
• Each element is a divisor of 𝑐$c$.
• All elements are distinct.
• For all 1≤𝑖<𝑛−1$1\le i<n-1$, gcd(𝑎𝑖,𝑎𝑖+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(𝑥,𝑦)$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$2$ divisors.

Input

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

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

The second line of each test case contains 𝑚$m$ integers 𝑏1,𝑏2,…,𝑏𝑚$b_1,b_2,\dots ,b_m$ (1≤𝑏𝑖<220$1\le b_i<2^{20}$) — exponents of corresponding prime factors of 𝑐$c$, so that 𝑐=𝑝𝑏11⋅𝑝𝑏22⋅…⋅𝑝𝑏𝑚𝑚$c=p_1^{b_1}\cdot p_2^{b_2}\cdot \dots \cdot p_m^{b_m}$ and 𝑛=(𝑏1+1)(𝑏2+1)…(𝑏𝑚+1)$n=(b_1+1)(b_2+1)\dots (b_m+1)$ hold. 𝑝𝑖$p_i$ is the 𝑖$i$-th smallest prime number.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Output

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

Otherwise, print 𝑛−1$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.