给定一个 $n \times m$ 的矩阵，你需要用 0 和 1 填充它，使得：

• 不能有四个连续的水平或垂直单元格填充相同的数字。
• 填充 1 的单元格形成一个连通区域。（如果两个单元格共享一条边，则它们是相邻的。如果对于每一对单元格，都能找到一条完全位于该组内且每一步仅从一个单元格移动到相邻单元格的路径，则称一组单元格是连通的。）

请构造一个满足上述条件且包含尽可能多 1 的矩阵。输出 1 的最大数量以及该矩阵。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n, m$ ($2 \le n, m \le 10^3$)。 保证所有测试用例的 $n \cdot m$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，第一行输出 1 的最大数量。然后在接下来的 $n$ 行中输出矩阵。如果存在多个解，输出任意一个即可。

样例

输入格式 1

3
2 2
3 4
3 8

输出格式 1

4
11
11
9
1110
1110
1110
18
11101110
10111011
11011011