CF1530B.Putting Plates

To celebrate your birthday you have prepared a festive table! Now you want to seat as many guests as possible.

The table can be represented as a rectangle with height $h$ and width $w$, divided into $h \times w$ cells. Let $(i, j)$ denote the cell in the $i$-th row and the $j$-th column of the rectangle ($1 \le i \le h$; $1 \le j \le w$).

Into each cell of the table you can either put a plate or keep it empty.

As each guest has to be seated next to their plate, you can only put plates on the edge of the table — into the first or the last row of the rectangle, or into the first or the last column. Formally, for each cell $(i, j)$ you put a plate into, at least one of the following conditions must be satisfied: $i = 1$, $i = h$, $j = 1$, $j = w$.

To make the guests comfortable, no two plates must be put into cells that have a common side or corner. In other words, if cell $(i, j)$ contains a plate, you can't put plates into cells $(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)$.

Put as many plates on the table as possible without violating the rules above.

为庆祝你的生日，你准备了一张节日餐桌！现在你想尽可能多地邀请客人入座。

餐桌可表示为一个高为 $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)$。

请在不违反上述规则的前提下，在餐桌上放置尽可能多的餐盘。

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

Each of the following $t$ lines describes one test case and contains two integers $h$ and $w$ ($3 \le h, w \le 20$) — the height and the width of the table.

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

接下来的 $t$ 行，每行描述一个测试用例，包含两个整数 $h$ 和 $w$（$3 \le h, w \le 20$）—— 表格的高度和宽度。

For each test case, print $h$ lines containing $w$ characters each. Character $j$ in line $i$ must be equal to $1$ if you are putting a plate into cell $(i, j)$, and $0$ otherwise. If there are multiple answers, print any.

All plates must be put on the edge of the table. No two plates can be put into cells that have a common side or corner. The number of plates put on the table under these conditions must be as large as possible.

You are allowed to print additional empty lines.

对于每个测试用例，输出 $h$ 行，每行包含 $w$ 个字符。第 $i$ 行中的第 $j$ 个字符必须为 $1$，当且仅当你将一个盘子放入单元格 $(i, j)$；否则为 $0$。若存在多个合法答案，输出任意一个即可。

所有盘子都必须放置在桌子的边缘上。任意两个盘子不能被放置在具有公共边或公共角的单元格中。在满足上述条件的前提下，桌面上放置的盘子数量应尽可能多。

允许额外输出空行。

For the first test case, example output contains the only way to put $6$ plates on the table.

For the second test case, there are many ways to put $4$ plates on the table, example output contains one of them.

Putting more than $6$ plates in the first test case or more than $4$ plates in the second test case is impossible.

对于第一个测试用例，示例输出包含了将 $6$ 个盘子放在桌子上的唯一方式。

对于第二个测试用例，将 $4$ 个盘子放在桌子上有多种方式，示例输出包含了其中一种。

在第一个测试用例中放置超过 $6$ 个盘子，或在第二个测试用例中放置超过 $4$ 个盘子，都是不可能的。