CF1801A.The Very Beautiful Blanket

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 OR

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