CF2138E2 Determinant Construction (Hard Version)

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](https://en.wikipedia.org/wiki/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.

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.

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 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.