**Ela and Prime GCD solution codeforces** – 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:

Table of Contents

## [Solution] Ela and Prime GCD solution codeforces

You are given an integer 𝑐c. Suppose that 𝑐c has 𝑛n divisors. You have to find a sequence with 𝑛−1n−1 integers [𝑎1,𝑎2,...𝑎𝑛−1][a1,a2,…an−1], which satisfies the following conditions:

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

## [Solution] Ela and Prime GCD solution codeforces

The first line contains one integer 𝑡t (1≤𝑡≤1041≤t≤104) – the number of test cases.

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

The second line of each test case contains 𝑚m integers 𝑏1,𝑏2,…,𝑏𝑚b1,b2,…,bm (1≤𝑏𝑖<2201≤bi<220) — exponents of corresponding prime factors of 𝑐c, so that 𝑐=𝑝𝑏11⋅𝑝𝑏22⋅…⋅𝑝𝑏𝑚𝑚c=p1b1⋅p2b2⋅…⋅pmbm and 𝑛=(𝑏1+1)(𝑏2+1)…(𝑏𝑚+1)n=(b1+1)(b2+1)…(bm+1) hold. 𝑝𝑖pi is the 𝑖i-th smallest prime number.

It is guaranteed that the sum of 𝑛⋅𝑚n⋅m over all test cases does not exceed 220220.

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

Otherwise, print 𝑛−1n−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 𝑎𝑖ai.

If there are multiple answers, print any of them.

## [Solution] Ela and Prime GCD solution codeforces

input

output

0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 -1 2 0 1 1 0 1 2 1 1 0

## [Solution] Ela and Prime GCD solution codeforces

In each test case, the values of 𝑐c are 66, 22, 3030, 1616, and 1212 in that order.

In the first test case, 11, 22, 33, 66 are divisors of 66. Here, sequences [2,6,3][2,6,3] and [3,6,2][3,6,2] can be answer. Permutation [3,2,6][3,2,6] is invalid because gcd(𝑎1,𝑎2)=1gcd(a1,a2)=1 is not a prime number.

In the forth test case, 11, 22, 44, 88, 1616 are divisors of 1616. Among the permutation of sequence [2,4,8,16][2,4,8,16], no valid answer exist.