E2. Determinant Construction (Hard Version)
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, the constraints on the side length of $$$M$$$ is smaller and the constraints on $$$t$$$ is larger. You can hack only if you solved all versions of this problem.

You are given a non-negative integer $$$x$$$. Your task is to construct a square matrix $$$M$$$ that satisfies all of the following conditions:

  • The side length of $$$M$$$ is at most $$$50$$$.
  • Each element of $$$M$$$ is either $$$-1$$$, $$$0$$$, or $$$1$$$.
  • The determinant of $$$M$$$ is equal to $$$x$$$.
  • Each row of $$$M$$$ can have at most $$$3$$$ non-zero positions, and each column of $$$M$$$ can have at most $$$3$$$ non-zero positions.

It can be proven that such a matrix always exists.

Input

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

The first and only line of each test case contains an integer $$$x$$$ ($$$0 \le x \le 10^7$$$) — the target value of the determinant.

Output

For each test case, output a single integer $$$n$$$ ($$$1\le n\le 50$$$) representing the side length of the square matrix $$$M$$$.

Then, output $$$n$$$ lines, the $$$i$$$-th line containing $$$n$$$ integers $$$M_{i, 1}, M_{i, 2}, \ldots, M_{i, n}$$$ ($$$M_{i, j} \in \{-1, 0, 1\}$$$), representing the elements of matrix $$$M$$$.

If there are multiple matrices $$$M$$$ satisfying the conditions, you may output any of them.

Example
Input
3
1
2
4
Output
1
1
2
1 -1 
1 1 
5
1 -1 0 0 0 
1 1 1 0 0 
0 1 1 -1 0 
0 0 1 1 -1 
0 0 0 1 1
Note

Note that in the third test case, the following solution: $$$$$$\begin{pmatrix} 1 & 1 & -1 & 1 \\ -1 & -1 & -1 & 1 \\ 1 & -1 & 0 & -1 \\ 1 & -1 & -1 & -1 \end{pmatrix}$$$$$$ is not valid as there are four non-zero positions in the first row of the matrix.