B. Расставьте тарелки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В честь вашего дня рождения вы подготовили праздничный стол! Теперь вы хотите посадить за него как можно больше гостей.

Стол можно схематично представить в виде прямоугольника с высотой $$$h$$$ и шириной $$$w$$$, разбитого на $$$h \times w$$$ ячеек. Будем обозначать через $$$(i, j)$$$ ячейку в $$$i$$$-й строке и $$$j$$$-м столбце прямоугольника ($$$1 \le i \le h$$$; $$$1 \le j \le w$$$).

В каждую ячейку можно либо поставить тарелку для гостя, либо оставить её пустой.

Поскольку гостя нужно посадить рядом со своей тарелкой, можно ставить тарелки только на границу стола — в первую или последнюю строку прямоугольника, либо в первый или последний столбец. Формально, для любой ячейки $$$(i, j)$$$, в которую ставится тарелка, должно выполняться хотя бы одно из следующих условий: $$$i = 1$$$, $$$i = h$$$, $$$j = 1$$$, $$$j = w$$$.

Чтобы гостям было максимально комфортно, никакие две тарелки не должны находиться в ячейках, имеющих общую сторону или угол. Иными словами, если в ячейке $$$(i, j)$$$ находится тарелка, нельзя ставить тарелки в ячейки $$$(i - 1, j)$$$, $$$(i, j - 1)$$$, $$$(i + 1, j)$$$, $$$(i, j + 1)$$$, $$$(i - 1, j - 1)$$$, $$$(i - 1, j + 1)$$$, $$$(i + 1, j - 1)$$$, $$$(i + 1, j + 1)$$$.

Поставьте как можно больше тарелок на стол, не нарушая описанные выше условия.

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

Во входных данных находятся несколько наборов входных данных. В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Каждая из следующих $$$t$$$ строк описывает один набор входных данных и содержит два целых числа $$$h$$$ и $$$w$$$ ($$$3 \le h, w \le 20$$$) — высоту и ширину стола.

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

Для каждого набора входных данных выведите $$$h$$$ строк по $$$w$$$ символов каждый. Символ $$$j$$$ в строке $$$i$$$ должен быть равен $$$1$$$, если в ячейку $$$(i, j)$$$ ставится тарелка, и $$$0$$$ в противном случае. Если существует несколько решений, выведите любое из них.

Все тарелки должны стоять на границе стола. Никакие две тарелки не могут стоять в ячейках, соседних по стороне или углу. Число тарелок, выставленных на стол при этих условиях, должно быть максимальным возможным.

Разрешается выводить дополнительные пустые строки.

Пример
Входные данные
3
3 5
4 4
5 6
Выходные данные
10101
00000
10101

0100
0001
1000
0010

010101
000000
100001
000000
101010
Примечание

В примере представлен единственный способ расставить $$$6$$$ тарелок на стол в первом наборе входных данных.

Во втором наборе входных данных есть много способов расставить $$$4$$$ тарелки, приведён один из них.

Поставить больше $$$6$$$ тарелок в первом наборе входных данных или $$$4$$$ тарелок во втором невозможно.