You are given an array $a$, consisting of $n$ positive integers. You are allowed to do the following operation:

• Select an array $b$ of size $n$ such that the following properties hold:
• $0 \leq b_i \leq a_i$ for each $1 \leq i \leq n$
  • There exists an index $1\leq i \lt n$ such that $b_1+b_2+\ldots+b_i=b_{i+1}+b_{i+2}+\ldots+b_n$. That is, the sum of the prefix of length $i$ is equal to the sum of the suffix of length $n-i$.
• Then, subtract $b_i$ from $a_i$ for each $1 \leq i \leq n$.

Your task is to change all the elements to $0$. Find the minimum number of operations required.

Then, output a way to perform the operations. If it is impossible to change all the elements of $a$ to $0$ no matter how many operations are used, print $-1$ instead. It can be shown that under the constraints of this problem, the smallest number of operations required is at most $17$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 5\cdot 10^4$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^{12}$) — denoting the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^4$.

Output

For each test case, output $-1$ if there is no solution.

Otherwise, first output an integer $s$ ($1 \leq s \leq 17$) – the minimum number of operations to change all the elements of $a$ to $0$.

Then, in the next $s$ lines, output $n$ integers in each line $b_1,b_2,\ldots,b_n (0 \leq b_i \leq a_i)$ — denoting the array $b$ for each operation.

After performing the operations, all the elements of $a$ should be changed to $0$.

Note

In the first test case, we can simply choose $b=a$ in our operation. This is valid because $b_1+b_2=b_3$.

In the second test case, it can be proven that it is impossible to change all the elements of $a$ to $0$.