A16251 | Fill in the Matrix

There is an empty matrix $M$ of size $n\times m$ .

Zhongkao examination is over, and Daniel would like to do some puzzle games. He is going to fill in the matrix $M$ using permutations of length $m$ . That is, each row of $M$ must be a permutation of length $m^\dagger$ .

Define the value of the $i$ -th column in $M$ as $v_i=\operatorname{MEX}(M_{1,i},M_{2,i},\ldots,M_{n,i})^\ddagger$ . Since Daniel likes diversity, the beauty of $M$ is $s=\operatorname{MEX}(v_1,v_2,\cdots,v_m)$ .

You have to help Daniel fill in the matrix $M$ and maximize its beauty.

$^\dagger$ A permutation of length $m$ is an array consisting of $m$ distinct integers from $0$ to $m-1$ in arbitrary order. For example, $[1,2,0,4,3]$ is a permutation, but $[0,1,1]$ is not a permutation ( $1$ appears twice in the array), and $[0,1,3]$ is also not a permutation ( $m-1=2$ but there is $3$ in the array).

$^\ddagger$ The $\operatorname{MEX}$ of an array is the smallest non-negative integer that does not belong to the array. For example, $\operatorname{MEX}(2,2,1)=0$ because $0$ does not belong to the array, and $\operatorname{MEX}(0,3,1,2)=4$ because $0$ , $1$ , $2$ and $3$ appear in the array, but $4$ does not.

The first line of input contains a single integer $t$ ( $1\le t\le 1000$ ) — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers $n$ and $m$ ( $1\le n,m\le 2\cdot 10^5$ ) — the size of the matrix.

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $2\cdot 10^5$ .

For each test case, in the first line output a single integer — the maximum beauty of $M$ .

Then output the matrix $M$ of size $n\times m$ — the matrix you find.

If there are multiple solutions, you may output any of them.