P15417 「yrOI R1」彼时蓝星


给你一个 $n \times m$ 的网格，你需要在网格上放置若干个国际象棋中的王，使得每个王的攻击范围内有且仅有 $1$ 个王。 你需要构造使得你放置王的数量最多，如果有多种方案，给出任意一种方案即可。 注：国际象棋中的王的攻击范围为距离它切比雪夫距离为 $1$ 的格子。

第一行一个数 $T$，代表数据组数。 接下来 $T$ 行每行两个数 $n,m$，代表一次查询。

对于每组数据，第一行一个数代表最多放置的王的个数。 接下来输出一个 $n$ 行 $m$ 列的 01 串 $a$，如果 $a_{i,j}=1$，则表示在 $(i,j)$ 放置了一个王。 如果你的答案的第一个数正确，你将会得到该测试点 $20\%$ 的分数。注意：请一定在后面输出一个方案（尽管可能是不合法的）。

**【数据范围】** **本题开启捆绑测试**。 + Subtask 1（5 pts）：$1 \le n,m \le 4$。 + Subtask 2（5 pts）：$1 \le n,m \le 10$。 + Subtask 3（5 pts）：$n=1$。 + Subtask 4（5 pts）：$n=2$。 + Subtask 5（5 pts）：无特殊限制。 对于所有数据，$1 \le T \le 10^5$，$1 \le n,m,\sum nm \le 10^6$。