Problem G

Matrix

Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

[Preliminaries]

(He who has already studied linear algebra may skip this part)

A matrix is composed of n*n elements. Formally,

is an n*n matrix.

for example, is a 2*2 matrix.

Two operations on matrices will be used in this problem:

1. A + k (A is an n*n matrix, k is an integer)

all the elements in the MAIN diagonal is added by k. that is

For example,

. A-k is defined A+(-k), so

2. A*B (both A and B are n*n matrices), let

, ,

and

then we have:

For example,

Well, I have no time to explain why matrix multiplication is defined like this. Please just remember it.

[Problem]

Find a matrix root of this equation:

(A + k₁)(A+k₂)(A+k₃)...(A+k_m) = O where k₁,k₂...k_m are distinct integers.

That is, EVERY ELEMENT OF the matrix computed from the left is zero.

for example,

is a matrix root of the equation(A+1)(A-5) = O，since

It can be proven that there are infinitely many solutions, however, I do not like trivial answer, so your answer must have at least (n*n)/2 non-zero elements.

Input

The first line contains the number of tests t(1<=t<=15). Each case contains two lines. The first line contains an integer m(1<=m<=30). The second line contains m integeres, representing k₁,k₂...k_m respectively. Absolute values of the integers are no greater than 100.

Output

For each test case, if no answer can be found, print -1. otherwise print n, indicating that you found an n*n matrix root. the following n lines should be the matrix. It is guaranteed that if there is an answer, the smallest possible n is not greater than 50, so your n should also NOT be greater than 50. The absolute value of integers you gave should not be larger than 1000.

Sample Input Output for Sample Input

1 -5

1 -5

1 4

2 3

1 4

2 3

Problemsetter: Rujia Liu, Member of Elite Problemsetters' Panel

Special thanks to Monirul Hasan