01回文

题号：NC306038
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Bingbong 拥有一个大小为 $n \times m$ 的 01 矩阵 $a$ ，矩阵的行从上至下依次为第 $1$ 行到第 $n$ 行，列从左至右依次为第 $1$ 列到第 $m$ 列，矩阵中每个元素 $a_{i,j}$ 的取值仅为 $\texttt{0}$ 或 $\texttt{1}$ 。

$\hspace{15pt}$ 对于矩阵中的每一个位置 $(i,j)$ ，请你判断并回答以下问题：
$\hspace{23pt}\bullet\,$ 从位置 $(i,j)$ 出发，是否存在一个非起点的位置 $(x,y)$ ，满足从 $(i,j)$ 到 $(x,y)$ 的某一条简单路径上的元素按路径顺序拼接形成的字符串为回文串。
$\hspace{15pt}$ 若存在满足条件的位置和路径，输出 $\texttt{Y}$ ，否则输出 $\texttt{N}$ 。每次回答相互独立，互不影响。

$\hspace{15pt}$ 每次移动，可以从当前位置 $(i,j)$ 到达与其相邻（上下左右）的一个位置 $(i', j')$ ，即 $|i-i'| + |j-j'| = 1$ 。

【名词解释】
$\hspace{15pt}$ 回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。
$\hspace{15pt}$ 简单路径：矩阵上任意两个坐标点之间的路径，且不经过重复的坐标点。更具体地，由矩阵中若干个不重复的坐标点构成的序列 $(p_1, p_2, \dots, p_k)$ 构成，其中 $p_i$ 与 $p_{i+1}$ 均是相邻的。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 ，代表数据组数，每组测试数据描述如下：

第一行两个整数 ，表示矩阵大小。
此后  行，第  行输入一个长度为 ，仅由字符  和  构成的字符串 ，表示矩阵第  行的元素。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，一共  行，每行输出一个长度为 ，仅由字符  和  构成的字符串，表示矩阵中每个位置是否可以满足题意。其中，第  个字符为  当且仅当位置  可以满足题意，否则为 。

示例1

输入

复制

输出

复制

YY
YY
YY
YY
YY
YY
NY
YY