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.

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.