题目描述

星绘是一位谜题大师。今天，她正在玩一款名叫“问号填充”的谜题。谜题由一个 $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 拼图。

如果有多种合法答案，输出任意一种。

请不要在行末输出多余空格，否则您的答案可能会被认为是错误的！

2
3
4

2
0 1 1
2 2 1
2 1 2
4
1 1 2 2
1 2 3 2
4 1 4 3
4 4 3 3

提示

样例数据解释如下。

:::align{center}

:::