CF2138E2.Determinant Construction (Hard Version)

这是该问题的困难版本。不同之处在于，本版本中 $M$ 的边长约束更小，$t$ 的约束更大。只有在你解决了所有版本的问题后才可以进行 hack。

给定一个非负整数 $x$。你的任务是构造一个满足以下所有条件的方阵 $M$：

• $M$ 的边长不超过 $50$。
• $M$ 的每个元素都是 $-1$、$0$ 或 $1$。
• $M$ 的行列式等于 $x$。
• $M$ 的每一行至多有 $3$ 个非零元素，每一列至多有 $3$ 个非零元素。

可以证明，总是存在满足要求的矩阵。

每组测试包含多个测试用例。第一行包含测试用例数 $t$，其中 $1 \leq t \leq 500$。接下来每个测试用例占一行，每行包含一个整数 $x$（$0 \leq x \leq 10^7$），即所需的行列式目标值。

对于每个测试用例，输出一个整数 $n$（$1 \leq n \leq 50$），表示所构造方阵 $M$ 的边长。

接下来输出 $n$ 行，每行 $n$ 个整数 $M_{i, 1}, M_{i, 2}, \ldots, M_{i, n}$，其中 $M_{i, j} \in \{-1, 0, 1\}$，表示矩阵 $M$ 的元素。

如果有多组满足条件的矩阵 $M$，可以输出任意一种。

注意在第三个测试用例中，以下解法：

$$\begin{pmatrix} 1 & 1 & -1 & 1 \\ -1 & -1 & -1 & 1 \\ 1 & -1 & 0 & -1 \\ 1 & -1 & -1 & -1 \end{pmatrix}$$

不合法，因为矩阵第一行有 $4$ 个非零元素。

由 ChatGPT 5 翻译