A. The Very Beautiful Blanket
bitmasks; constructive algorithms
Kirill wants to weave the very beautiful blanket consisting of \(n \times m\) of the same size square patches of some colors. He matched some non-negative integer to each color. Thus, in our problem, the blanket can be considered a \(B\) matrix of size \(n \times m\) consisting of non-negative integers.Kirill considers that the blanket is very beautiful, if for each submatrix \(A\) of size \(4 \times 4\) of the matrix \(B\) is true: \(A_{11} \oplus A_{12} \oplus A_{21} \oplus A_{22} = A_{33} \oplus A_{34} \oplus A_{43} \oplus A_{44},\) \(A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42},\)where \(\oplus\) means bitwise exclusive ORKirill asks you to help her weave a very beautiful blanket, and as colorful as possible!He gives you two integers \(n\) and \(m\). Your task is to generate a matrix \(B\) of size \(n \times m\), which corresponds to a very beautiful blanket and in which the number of different numbers maximized.
The first line of input data contains one integer number \(t\) (\(1 \le t \le 1000\)) — the number of test cases.The single line of each test case contains two integers \(n\) and \(m\) \((4 \le n, \, m \le 200)\) — the size of matrix \(B\).It is guaranteed that the sum of \(n \cdot m\) does not exceed \(2 \cdot 10^5\).
For each test case, in first line output one integer \(cnt\) \((1 \le cnt \le n \cdot m)\) — the maximum number of different numbers in the matrix.Then output the matrix \(B\) \((0 \le B_{ij} < 2^{63})\) of size \(n \times m\). If there are several correct matrices, it is allowed to output any one.It can be shown that if there exists a matrix with an optimal number of distinct numbers, then there exists among suitable matrices such a \(B\) that \((0 \le B_{ij} < 2^{63})\).
In the first test case, there is only 4 submatrix of size \(4 \times 4\). Consider a submatrix whose upper-left corner coincides with the upper-left corner of the matrix \(B\):\( \left[ {\begin{array}{cccc} 9740 & 1549 & 9744 & 1553 \\ 1550 & 1551 & 1554 & 1555 \\ 10252 & 2061 & 10256 & 2065 \\ 2062 & 2063 & 2066 & 2067 \\ \end{array} } \right] \)\(9740 \oplus 1549 \oplus 1550 \oplus 1551\) \(=\) \(10256 \oplus 2065 \oplus 2066 \oplus 2067\) \(=\) \(8192\);\(10252 \oplus 2061 \oplus 2062 \oplus 2063\) \(=\) \(9744 \oplus 1553 \oplus 1554 \oplus 1555\) \(=\) \(8192\).So, chosen submatrix fits the condition. Similarly, you can make sure that the other three submatrices also fit the condition.