P13958 [ICPC 2023 Nanjing R] 谜题：问号
题目描述
星绘是一位谜题大师。今天，她正在玩一款名叫“问号填充”的谜题。谜题由一个 $n$ 行 $n$ 列的网格，以及许多问号拼图（QM 拼图）组成。一片 QM 拼图占据 $4$ 个格子，如下图所示。
:::align{center}
一片 QM 拼图（它看起来像一个问号，应该吧？）
:::
整片 QM 拼图必须全部位于网格内部，拼图可以旋转 $90$ 度的倍数或翻面。更精确地，共有 $8$ 种 QM 拼图，如下图所示。
:::align{center}
:::
任意两片 QM 拼图不能占据同一个格子。谜题的目标是在 $n \times n$ 的网格中放入尽可能多的 QM 拼图。
星绘想知道您能否成功解开谜题。
输入格式
有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：
第一行输入一个整数 $n$（$1 \leq n \leq 2 \times 10^3$）表示网格的大小。
保证所有数据 $n^2$ 之和不超过 $5 \times 10^6$。
输出格式
对于每组数据：
首先输出一行一个整数表示最多能在网格中放入几片 QM 拼图。
接下来输出 $n$ 行。每一行包含由单个空格分隔的 $n$ 个整数。第 $i$ 行的第 $j$ 个整数 $a_{i,j}$ 表示位于第 $i$ 行第 $j$ 列的格子属于第 $a_{i,j}$ 片 QM 拼图。如果 $a_{i,j}$ 为 $0$，则这个格子是空的，不属于任何 QM 拼图。
如果有多种合法答案，输出任意一种。
请不要在行末输出多余空格，否则您的答案可能会被认为是错误的！
说明/提示
样例数据解释如下。
:::align{center}
:::