说明

给你一个 $n \times m$ 的网格，你需要在网格上放置若干个国际象棋中的王，使得每个王的攻击范围内有且仅有 $1$ 个王。

你需要构造使得你放置王的数量最多，如果有多种方案，给出任意一种方案即可。

注：国际象棋中的王的攻击范围为距离它切比雪夫距离为 $1$ 的格子。

输入格式

第一行一个数 $T$，代表数据组数。

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

输出格式

对于每组数据，第一行一个数代表最多放置的王的个数。

接下来输出一个 $n$ 行 $m$ 列的 01 串 $a$，如果 $a_{i,j}=1$，则表示在 $(i,j)$ 放置了一个王。

如果你的答案的第一个数正确，你将会得到该测试点 $20\%$ 的分数。注意：请一定在后面输出一个方案（尽管可能是不合法的）。

3
2 2
3 4
3 3

2
10
10
6
1101
0001
1100
4
110
000
110

提示

【数据范围】

本题开启捆绑测试。

• 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$。