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.

基里尔想要编织一条极其美丽的毛毯，该毛毯由 $n \times m$ 个相同大小的正方形色块组成。他为每种颜色分配了一个非负整数。因此，在本题中，毛毯可视为一个 $n \times m$ 的矩阵 $B$，其元素均为非负整数。

基里尔认为，当且仅当矩阵 $B$ 的每个 $4 \times 4$ 子矩阵 $A$ 均满足以下两个条件时，该毛毯是“极其美丽”的：

• $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},$

其中 $\oplus$ 表示按位异或运算。

基里尔请你帮助他编织一条“极其美丽”的毛毯，并且尽可能地丰富多彩！

他给你两个整数 $n$ 和 $m$。

你的任务是构造一个 $n \times m$ 的矩阵 $B$，使其对应一条“极其美丽”的毛毯，且其中不同数字的个数最大化。

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

输入数据的第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

每个测试用例的单独一行包含两个整数 $n$ 和 $m$（$4 \le n, \, m \le 200$）—— 表示矩阵 $B$ 的尺寸。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $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} \lt 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} \lt 2^{63})$.

对于每个测试用例，首先在第一行输出一个整数 $cnt$ $(1 \le cnt \le n \cdot m)$ —— 矩阵中不同数字的最大个数。

然后输出一个大小为 $n \times m$ 的矩阵 $B$ $(0 \le B_{ij} \lt 2^{63})$。若存在多个正确的矩阵，则输出任意一个均可。

可以证明：若存在一个具有最优不同数字个数的矩阵，则在所有满足条件的矩阵中，必存在某个矩阵 $B$ 满足 $(0 \le B_{ij} \lt 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.

在第一个测试用例中，仅有 4 个大小为 $4 \times 4$ 的子矩阵。考虑一个其左上角与矩阵 $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$。

因此，所选子矩阵满足条件。类似地，你可以验证其余三个子矩阵也均满足该条件。