为了庆祝你的生日,你准备了一张节日餐桌!现在您想要容纳尽可能多的客人。
该表格可以表示为一个高度为 $$$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$$$ 字符。如果将盘子放入单元格 $$$(i, j)$$$ 中,则 $$$i$$$ 行中的字符 $$$j$$$ 必须等于 $$$1$$$,否则为 $$$0$$$。如果有多个答案,请打印其中一个。
所有盘子必须放在桌子的边缘。不能将两块板放入具有公共侧面或公共角的单元中。在这种情况下,桌上摆放的盘子数量必须尽可能多。
您可以打印额外的空行。
示例
输入 #1
3 3 5 4 4 5 6
输出 #1
10101 00000 10101 0100 0001 1000 0010 010101 000000 100001 000000 101010
注意
对于第一个测试用例,示例输出包含将 $$$6$$$ 盘子放在桌子上的唯一方法。
对于第二个测试用例,有多种方法可以将 $$$4$$$ 盘子放在桌子上,示例输出包含其中一种。
在第一个测试用例中放置超过 $$$6$$$ 板或在第二个测试用例中放置超过 $$$4$$$ 板是不可能的。