题目背景

小林最近迷上了扫雷游戏。

题目描述

一个扫雷游戏可以被抽象成一个 $n$ 行 $m$ 列的字符矩阵，不妨记第 $i$ 行第 $j$ 列的字符为 $S_{i,j}$。

若 $S_{i,j}=\texttt{*}$，表示格子 $(i,j)$ 上有一个地雷；

若 $S_{i,j}=\texttt{?}$，表示格子 $(i,j)$ 情况未知；

若 $S_{i,j}\in [0,8]$，表示格子 $(i,j)$ 周围的 $8$ 个格子中有 $S_{i,j}$ 个地雷（这个格子本身没有地雷）。 形式化地说，记

$$f(i,j)=\begin{cases} 1, & (i,j)\text{ 上有地雷} \\ 0, & \text{其他情况} \\ \end{cases} $$

特别地，对于超出棋盘边界的情况，规定 $f(i,j)=0$。 则 $\displaystyle S_{i,j}=\sum_{p=-1}^1\sum_{q=-1}^1 f(i+p,j+q)$。

给定一个棋盘，你可以任意决定每个 $\texttt{?}$ 格子上是否有炸弹。你想要知道是否存在方案使得这个棋盘是合法的。 我们定义一个棋盘合法，当且仅当填有数字 $x$ 的格子周围的八个格子上恰好有 $x$ 个炸弹。

你需要解决 $T$ 组数据。

输入格式

本题单个测试点内含多组测试数据。

第一行，一个正整数 $T$，代表数据组数；

对于每组数据，输入 $(n+1)$ 行：

• 第一行，两个正整数 $n,m$，描述棋盘的行数和列数；
• 接下来 $n$ 行，第 $(i+1)$ 行的第 $j$ 个字符描述 $S_{i,j}$。

输出格式

对于每组数据，输出一行。

若存在合法的方案，输出 YES；否则输出 NO。

3
2 2
**
2?
2 2
*1
3?
2 2
**
21

YES
NO
NO

提示

对于第一组数据：问号处选择不填是一种合法方案。可以证明这是唯一的合法方案。

本题采用捆绑测试。

• Subtask 1（20pts）：至多存在 $1$ 组 $(i,j)$，使得 $S_{i,j}=\texttt{?}$；
• Subtask 2（80pts）：无额外约束。

对于 $100\%$ 的数据，保证：

• $1\le T,n,m\le 10$；
• 至多存在 $10$ 组 $(i,j)$，使得 $S_{i,j}=\texttt{?}$；
• $\forall 1\le i\le n,1\le j\le m$，保证 $S_{i,j}\in\{0,1,2,3,4,5,6,7,8,\texttt{?},\texttt{*}\}$。