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

Кирилл хочет связать очень красивое одеяло, состоящее из $$$n \times m$$$ одинакового размера квадратных лоскутков разных цветов. Каждому цвету он сопоставил некоторое неотрицательное целое число. Таким образом, в нашей задаче одеяло можно считать матрицей $$$B$$$ размера $$$n \times m$$$.

Кирилл считает одеяло очень красивым, если для каждой подматрицы $$$A$$$ размера $$$4 \times 4$$$ матрицы $$$B$$$ верно:

  • $$$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$$$. Ваша задача — сгенерировать очень красивую матрицу $$$B$$$ размера $$$n \times m$$$, в которой количество различных чисел максимально.

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

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

В единственной строке каждого набора входных данных заданы два целых числа $$$n$$$ и $$$m$$$ $$$(4 \le n, \, m \le 200)$$$ — числа, задающие размер матрицы $$$B$$$.

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

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

Для каждого набора входных данных в первой строке выведите одно целое число $$$cnt$$$ $$$(1 \le cnt \le n \cdot m)$$$ — максимальное количество различных чисел в матрице.

Затем выведите саму матрицу $$$B$$$ $$$(0 \le B_{ij} < 2^{63})$$$ размера $$$n \times m$$$. Если подходящих матриц несколько, разрешается вывести любую.

Можно показать, что если существует матрица с оптимальным количеством различных чисел, то существует среди подходящих матриц такая $$$B$$$, что $$$(0 \le B_{ij} < 2^{63})$$$.

Пример
Входные данные
4
5 5
4 4
4 6
6 6
Выходные данные
25
9740 1549 9744 1553 9748
1550 1551 1554 1555 1558
10252 2061 10256 2065 10260
2062 2063 2066 2067 2070
10764 2573 10768 2577 10772
16
3108 3109 3112 3113
3110 3111 3114 3115
3620 3621 3624 3625
3622 3623 3626 3627
24
548 549 552 553 556 557
550 551 554 555 558 559
1060 1061 1064 1065 1068 1069
1062 1063 1066 1067 1070 1071
36
25800 25801 25804 25805 25808 25809
25802 4294993099 25806 4294993103 25810 4294993107
26312 26313 26316 26317 26320 26321
26314 4294993611 26318 4294993615 26322 4294993619
26824 26825 26828 26829 26832 26833
26826 4294994123 26830 4294994127 26834 4294994131
Примечание

Разберем первый пример. Здесь есть всего 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$$$.

Таким образом, выбранная подматрица подходит под условие. Аналогично можно удостовериться в том, что другие три подматрицы тоже подходят под условие.