Matrix Coloring

题号：NC311833
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个 $n \times n$ 的 $01$ 矩阵，其中 $0$ 表示白色格子， $1$ 表示黑色格子。

$\hspace{15pt}$ 矩阵会按照以下规则进行演化：对于每个白色格子，如果它四方向相邻（上、下、左、右）的格子中，黑色格子的数量至少为 $2$ ，并且这些黑色格子中存在至少一对在八方向连通（即可以上下左右或斜对角相邻连通）的意义下是连通的，那么这个白色格子将在下一步变为黑色。
$\hspace{15pt}$ 注意：
$\hspace{23pt}\bullet\$ 1. 演化是同步的：所有满足条件的白色格子会在同一时间步变为黑色。
$\hspace{23pt}\bullet\$ 2. 黑色格子永远不会变回白色。
$\hspace{23pt}\bullet\$ 3. 连通性是针对整个矩阵的黑色格子而言的，判断时使用八方向相邻（即一个格子的八个邻居）。

$\hspace{15pt}$ 你的任务就是求出：当矩阵不再变化（即没有新的白色格子满足条件）时，最终的矩阵是什么样子。

输入描述:

第一行一个整数 ，表示测试数据组数。

对于每组数据：
第一行一个整数 。
接下来  行，每行一个长度为  的字符串，只包含字符  和 ，表示初始矩阵。

保证所有测试数据的  之和不超过 。

输出描述:

对于每组数据，输出  行，每行一个长度为  的字符串，表示最终稳定时的矩阵。

示例1

输入

复制

输出

复制

说明

第一组数据：初始矩阵为棋盘格。每个  周围有  个 ，且这些  通过八方向连通（实际上所有  都是八方向连通的），因此所有  在第一轮都被染黑，得到全 。