A128496.无限水

这个玩家梦见了什么？
他梦见了阳光与草木，梦见了火与水。他梦见他创造，亦梦见他毁灭。他梦见他狩猎，亦被狩猎。他梦见了避身之处。
……
曲终人散，黄粱一梦。玩家开始了新的梦境。玩家再次做起了梦，更好的梦。玩家就是宇宙。玩家就是爱。
你就是那个玩家。醒来吧。

——Minecraft《终末之诗》

一切都结束了……吗？

Steve 修建了一个长 $n$ 格、宽 $m$ 格的水池，他想往这个水池中注满水。具体地，Steve 每次可以将一个冰块放置在某个格子中，把这个格子变成水源。同时在任意时刻，如果某个格子周围四个格子中有大于等于两个格子是水源，这个格子也会转化为水源。

请你帮 Steve 找到一种放置尽量少的冰块的方案，使得最后全部 $n\times m$ 个格子都成为水源。

每个测试点包含多组测试数据。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数。对于每组测试数据：

第一行包含两个正整数 $n,m$，表示水池的大小。

本题采用 Special Judge*，你只需要构造出任意一种符合条件的方案。同时根据你放置冰块数量的多少，你可以得到部分分，具体标准见下方的【评分方式】。

对于每组测试数据，输出 $n$ 行，其中的第 $i$ 行包含一个长度为 $m$ 的 $01$ 串 $s_{i,0}s_{i,1}\cdots s_{i,m}$。记格子 $(i,j)$ 为第 $i$ 行的第 $j$ 个格子，若 $s_{i,j}=1$，表示 Steve 要格子 $(i,j)$ 中放置冰块，否则表示不在格子 $(i,j)$ 中放置冰块。

【评分方式】

本题只有一份输入文件，但由于 ACGO 的限制，该题目分为 $10$ 个测试点，对于第 $i$ 个测试点，如果你在该输入文件中的得分大于等于 $10i$，则该测试点视为通过，否则视为不通过。

对于该输入文件中的每一组测试数据 $n,m$，若你构造的放置冰块的方案不合法，你在该组测试数据中获得 $0$ 分；否则设你放置了 $x$ 个冰块，该组测试数据至少要放置 $y$ 个冰块：

• 若 $x=y$，你能够获得 $100$ 分；
• 否则若 $x\le\max(n,m)$，你能获得 $80$ 分；
• 否则若 $x\le n+m$，你能获得 $60$ 分；
• 否则若 $x\le 2(n+m)$，你能获得 $50$ 分；
• 否则若 $x\le \lfloor 0.3nm\rfloor$，你能获得 $30$ 分；
• 否则若 $x\le \lfloor 0.6nm\rfloor$，你能获得 $20$ 分；
• 否则若 $x\le nm$，你能获得 $10$ 分。

你在该输入文件中的得分为所有测试数据得分中的最小值。

【样例解释】

对于第一组测试数据，放置了六个冰块，使格子 $(1,1),(1,2),(1,3),(2,1),(2,2),(3,1)$ 成为水源。格子 $(2,3),(3,2)$ 由于周围有两个水源，首先被转化为水源。因此格子 $(3,3)$ 周围有两个转化得来的水源 $(2,3),(3,2)$，进而被转化为水源。

注意该样例不满足实际测试中 $n,m\ge 10$ 的条件，且构造出的方案也无法拿到满分。

【数据范围】

对于 $100\%$ 的测试点，保证：$1\le T\le10^3$，$10 \le n,m \le 200$，单个测试点中所有测试数据的 $nm$ 之和不超过 $2\times10^5$。