Valid Minesweeper Board

You are given an n × m Minesweeper board represented as a character matrix. The cell in the i-th row and j-th column is denoted by \(S_{i,j}\). There are three types of cells:

• If \(S_{i,j} = \texttt{*}\), then the cell \((i,j)\) contains a bomb.
• If \(S_{i,j} = \texttt{?}\), then the status of cell \((i,j)\) is unknown and you can decide whether or not to place a bomb there.
• If \(S_{i,j}\) is a digit between 0 and 8 inclusive, then it indicates that among the 8 cells surrounding \((i,j)\) there are exactly \(S_{i,j}\) bombs. (Note that the cell containing a digit does not have a bomb.)

Formally, define the function \[ f(i,j)=\begin{cases} 1, & \text{if cell } (i,j) \text{ contains a bomb},\\ 0, & \text{otherwise}. \end{cases} \] For cells outside the board, we define \(f(i,j)=0\). Then for a cell with a digit (which implies no bomb in that cell) we have \[ S_{i,j} = \sum_{p=-1}^{1}\sum_{q=-1}^{1} f(i+p,j+q). \]

Your task is to decide whether there exists an assignment (i.e. for every \(\texttt{?}\) cell, choose to place a bomb or not) such that the board becomes valid. We say the board is valid if and only if for every cell with a digit \(x\), exactly \(x\) bombs are present in its 8 adjacent cells.

You need to solve \(T\) test cases.

inputFormat

The first line contains a single integer \(T\) (the number of test cases). For each test case, the first line contains two integers \(n\) and \(m\) ( \(1 \le n,m\le \) small limits) representing the number of rows and columns of the board. Each of the next \(n\) lines contains a string of length \(m\) consisting of characters: digits (0–8), *, or ?.

outputFormat

For each test case, output a single line containing YES if there exists a valid assignment for the board; otherwise, output NO.

sample

3
3 3
1?1
?*?
1?1
2 2
0*
2?
3 3
???
?*?
???

YES
NO
YES