[EC Final 2022] Aqre

**【题目描述】** 给定一个 $n \times m$ 矩阵，你需要用 $0$ 和 $1$ 填充它，使得满足以下条件： - 不能有**四个**连续的水平或垂直单元格填有相同的数字。 - 填有 $1$ 的单元格形成一个连通区域。（如果它们共享一个边，则两个单元格是相邻的。如果对于每对单元格，可以找到一条完全位于该区域内的连接两个单元格的路径，并且每一步只能从一个单元格移动到相邻的单元格，则一组单元格被称为连通的。） 请构造一个满足上述条件且具有尽可能多的 $1$ 的矩阵。输出 $1$ 的最大数量以及该矩阵。 **【输入格式】** 第一行包含一个整数 $T~(1\leq T\leq 10^3)$，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n, m~(2\leq n, m\leq 10^3)$。 保证所有测试用例中 $n\cdot m$ 的总和不超过 $10^6$。 **【输出格式】** 对于每个测试用例，输出第一行中 $1$ 的最大数量。然后在接下来的 $n$ 行中输出矩阵。如果有多种解决方案，则输出任意一个。 翻译来自于：[ChatGPT](https://chatgpt.com/)

Given an $n \times m$ matrix, you need to fill it with $0$ and $1$, such that: - There cannot be **four** consecutive horizontal or vertical cells filled with the same number. - The cells filled with $1$ form a connected area. (Two cells are adjacent if they share an edge. A group of cells is said to be connected if for every pair of cells it is possible to find a path connecting the two cells which lies completely within the group, and which only travels from one cell to an adjacent cell in each step.) Please construct a matrix satisfying the conditions above and has as many $1$s as possible. Output the maximum number of $1$s, and the matrix.

The first line contains an integer $T~(1\leq T\leq 10^3)$ -- the number of test cases. For each test case, the first line contains two integers $n, m~(2\leq n, m\leq 10^3)$. ### It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^6$.

For each test case, output the maximum number of $1$s in the first line. Then output the matrix in the following $n$ lines. If there are multiple solution, output any.

3
2 2
3 4
3 8

4
11
11
9
1110
1110
1110
18
11101110
10111011
11011011