{"raw_statement":[{"iden":"statement","content":"Given an $n \\times m$ matrix, you need to fill it with $0$ and $1$, such that:\n\n- There cannot be **four** consecutive horizontal or vertical cells filled with the same number.\n- 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.)\n\nPlease 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."},{"iden":"input","content":"The first line contains an integer $T~(1\\leq T\\leq 10^3)$ -- the number of test cases.\n\nFor each test case, the first line contains two integers $n, m~(2\\leq n, m\\leq 10^3)$.\n\n### It is guaranteed that the sum of $n\\cdot m$ over all test cases does not exceed $10^6$."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[["3\n2 2\n3 4\n3 8\n","4\n11\n11\n9\n1110\n1110\n1110\n18\n11101110\n10111011\n11011011\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}