A. Заполните матрицу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имеется пустая матрица $$$M$$$ размера $$$n\times m$$$.

Экзамен закончился, и Daniel хотел бы заняться головоломками. Он собирается заполнить матрицу $$$M$$$ перестановками длины $$$m$$$. То есть каждая строка $$$M$$$ должна быть перестановкой длины $$$m^\dagger$$$.

Определим значение $$$i$$$-го столбца в $$$M$$$ как $$$v_i=\operatorname{MEX}(M_{1,i},M_{2,i},\ldots,M_{n,i})^\ddagger$$$. Поскольку Daniel любит разнообразие, то красота $$$M$$$ равна $$$s=\operatorname{MEX}(v_1,v_2,\cdots,v_m)$$$.

Вы должны помочь Daniel заполнить матрицу $$$M$$$ и максимизировать её красоту.

$$$^\dagger$$$ Перестановка длины $$$m$$$ — это массив, состоящий из $$$m$$$ различных целых чисел от $$$0$$$ до $$$m-1$$$, расположенных в произвольном порядке. Например, $$$[1,2,0,4,3]$$$ является перестановкой, но $$$[0,1,1]$$$ не является перестановкой ($$$1$$$ встречается в массиве дважды), и $$$[0,1,3]$$$ также не является перестановкой ($$$m-1=2$$$, но в массиве есть $$$3$$$).

$$$^\ddagger$$$ $$$\operatorname{MEX}$$$ массива — это наименьшее неотрицательное целое число, не принадлежащее массиву. Например, $$$\operatorname{MEX}(2,2,1)=0$$$, так как $$$0$$$ не принадлежит массиву, и $$$\operatorname{MEX}(0,3,1,2)=4$$$, так как $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ в массиве есть, а $$$4$$$ нет.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\le t\le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\le n,m\le 2\cdot 10^5$$$) — размер матрицы.

Гарантируется, что сумма $$$n\cdot m$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в первой строке выведите одно целое число — максимальную красоту $$$M$$$.

Затем выведите матрицу $$$M$$$ размера $$$n\times m$$$ — матрицу, которую вы нашли.

Если существует несколько решений, вы можете вывести любое из них.

Пример
Входные данные
4
4 3
1 16
6 6
2 1
Выходные данные
3
1 0 2
0 2 1
1 0 2
0 2 1
2
14 7 15 4 10 0 8 6 1 2 3 5 9 11 12 13 
6
3 0 1 4 2 5 
5 2 1 0 4 3 
1 3 2 4 5 0 
4 1 3 2 5 0 
4 2 5 3 0 1 
2 4 0 5 1 3
0
0
0
Примечание

В первом наборе входных данных:

  • $$$v_1=\operatorname{MEX}(1,0,1,0)=2$$$;
  • $$$v_2=\operatorname{MEX}(0,2,0,2)=1$$$;
  • $$$v_3=\operatorname{MEX}(2,1,2,1)=0$$$.

Таким образом, $$$s=\operatorname{MEX}(2,1,0)=3$$$.

Можно доказать, что $$$3$$$ является максимально возможной красотой $$$M$$$.

Во втором наборе входных данных при любой перестановке $$$s=2$$$.

В третьем наборе входных данных:

  • $$$v_1=\operatorname{MEX}(3,5,1,4,4,2)=0$$$;
  • $$$v_2=\operatorname{MEX}(0,2,3,1,2,4)=5$$$;
  • $$$v_3=\operatorname{MEX}(1,1,2,3,5,0)=4$$$;
  • $$$v_4=\operatorname{MEX}(4,0,4,2,3,5)=1$$$;
  • $$$v_5=\operatorname{MEX}(2,4,5,5,0,1)=3$$$;
  • $$$v_6=\operatorname{MEX}(5,3,0,0,1,3)=2$$$.

Таким образом, $$$s=\operatorname{MEX}(0,5,4,1,3,2)=6$$$.