CF2219E Weird Chessboard

考虑一个大小为 $n \times n$ 的国际象棋棋盘（一张网格）。你希望在这张棋盘上尽可能多地放置棋子。这些棋子的行为如下：如果我们将左上角的格子记作 $(1,1)$，那么放在 $(i,j)$ 的一枚棋子可以攻击所有满足 $x \ge i$ 且 $y \ge j$ 的格子，除了它自己所在的 $(i,j)$。 例如，在一个 $10 \times 10$ 的棋盘上，放在 $(3,4)$ 的一枚棋子可以攻击下图高亮的格子：  给定一个已放置棋子的位置集合。我们称某个格子是“优质”的，如果攻击该格子的棋子数量是偶数。 请你构造一种放置棋子的方案，使得每个格子都是优质的（无论该格子自身是否有棋子），并且棋盘上至少有 $\left\lfloor \frac{n^2}{10} \right\rfloor \times 3$ 枚棋子。

每组测试包含多个测试用例。第一行包含测试用例数 $t$，$(1 \le t \le 50)$。各组测试数据描述如下。 每组测试用例的第一行包含一个整数 $n$，$(1 \le n \le 5000)$。 保证所有测试用例中 $n^2$ 的和不超过 $25\,000\,000 = 5000^2$。

对于每组测试用例，输出 $n$ 行，每行 $n$ 个由空格隔开的整数，其中 $1$ 表示该格子上放有棋子，$0$ 表示该格子上没有棋子。 第 $i$ 行第 $j$ 个整数对应格子 $(i, j)$。

下面是一个 $3 \times 3$ 的棋盘，每个格子都是优质的。 格子 $(3, 3)$ 是优质的，因为其被 $(1, 3)$、$(2, 3)$、$(2, 2)$、$(3, 1)$ 这四个带棋子的格子攻击，共有 4 个，个数是偶数。 格子 $(1, 3)$ 是优质的，因为没有棋子攻击它，攻击该格子的棋子数量是 0。 $(3, 2)$ 也是优质的，要注意，即使这个格子上没有棋子，也要求它是优质的。 由 ChatGPT 5 翻译