这是问题的困难版本。版本之间的区别在于,在该版本中,$$$M$$$ 的边长约束较小,而$$$t$$$ 的边长约束较大。只有解决了该问题的所有版本,您才能破解。
给你一个非负整数$$$x$$$。您的任务是构造一个满足以下所有条件的方阵 $$$M$$$:
- $$$M$$$ 的边长最多为 $$$50$$$。
- $$$M$$$ 的每个元素是 $$$-1$$$、$$$0$$$ 或 $$$1$$$。
- $$$M$$$ 的行列式等于 $$$x$$$。
- $$$M$$$ 的每一行最多可以有 $$$3$$$ 非零位置,$$$M$$$ 的每一列最多可以有 $$$3$$$ 非零位置。
可以证明这样的矩阵总是存在。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含一个整数 $$$x$$$ ($$$0 \le x \le 10^7$$$) — 行列式的目标值。
输出
对于每个测试用例,输出一个整数 $$$n$$$ ($$$1\le n\le 50$$$) 表示方阵 $$$M$$$ 的边长。
然后,输出$$$n$$$行,第$$$i$$$行包含$$$n$$$整数$$$M_{i, 1}, M_{i, 2}, \ldots, M_{i, n}$$$ ($$$M_{i, j} \in \{-1, 0, 1\}$$$),代表矩阵的元素$$$M$$$。
如果有多个矩阵 $$$M$$$ 满足条件,则可以输出其中任何一个。
示例
输入复制
3124
输出复制
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
注意
请注意,在第三个测试用例中,以下解决方案: $$\begin{pmatrix} 1 & 1 & -1 & 1 \\ -1 & -1 & -1 & 1 \\ 1 & -1 & 0 & -1 \\ 1 & -1 & -1 & -1 \end{pmatrix}$$ 无效,因为矩阵的第一行中有四个非零位置。