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