题目描述:

你拥有一个大小为 $n \times m$ 的 $01$ 矩阵 $a$。矩阵的行从上至下依次为第 $1$ 到第 $n$ 行，列从左至右依次为第 $1$ 到第 $m$ 列。矩阵中每个元素 $a_{i,j}$ 的取值仅为 $0$ 或 $1$。 对于矩阵中的每一个位置 $(i,j)$，请你判断并回答以下问题： 从位置 $(i,j)$ 出发，是否存在一个非起点的位置 $(x,y)$，满足从 $(i,j)$ 到 $(x,y)$ 的某一条简单路径上的元素按路径顺序拼接形成的字符串为回文串。 若存在满足条件的位置和路径，输出 Y，否则输出 N。每次回答相互独立，互不影响。

名词解释：

• 回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。
• 简单路径：指由矩阵中若干个不重复的坐标点构成的序列 $(p_1, p_2, \dots, p_k)$，其中 $p_i$ 与 $p_{i+1}$ 相邻（上下左右距离为 $1$）。

输入格式:

输入第一行给出一个正整数 $T (1 \leq T \leq 10^4)$，代表数据组数。 对于每组测试数据： 第一行包含两个整数 $n, m (1 \leq n, m \leq 10^6 且 1 \leq n \times m \leq 10^6)$，表示矩阵的大小。 随后 $n$ 行，每行输入一个长度为 $m$ 的字符串，由字符 $0$ 和 $1$ 组成。 保证所有测试数据的 $n \times m$ 之和不超过 $10^6$。

输出格式:

对于每组测试数据，输出 $n$ 行，每行一个长度为 $m$ 的字符串。 若位置 $(i, j)$ 存在符合条件的回文简单路径，则对应位置输出 Y，否则输出 N。

输入样例:

4
2 2
11
11
2 2
00
00
2 2
10
01
2 2
10
00

输出样例:

YY
YY
YY
YY
YY
YY
NY
YY

数据范围:

$1 \leq T \leq 10^4$ $1 \leq n, m \leq 10^6$ $\sum (n \times m) \leq 10^6$ 每个位置的移动方向限制为：上下左右四个方向。