Description

Honey Kingdom, a nation built by bees, all areas are developed in a regular hexagonal (正六邊形) pattern. To facilitate development, they use a unique coordinate system where each hexagonal cell is represented by coordinate (x,y) as shown below:

The map is structured such that the first row has coordinates:

(1,1) , (1,2) , ... , (1,M)

The second row then has:

(2,1) , (2,2) , ... , (2,M)

...

In this system, each cell (x,y) is positioned between (x−1,y) and (x−1,y+1).

For any cell located at (x,y), its neighboring cells are:

(x-1,y) , (x-1,y+1) , (x,y-1) , (x,y+1) , (x+1,y-1) , (x+1,y)

Now, Bee Agent User333 has been assigned T missions, each involving a different map. On each map, the starting point is always (1,1) and the destination is (N,M).

Each cell on the map contains specific information denoted by A_i,j​ :

• If A_i,j = 'X', the cell is mostly water. For safety reasons, User333 cannot travel across water.
• If A_i,j = '0', the cell is open grassland, which User333 can freely cross.
• If A_i,j​ is a number '2' or '3', it indicates the presence of a "magic circle" with a "teleport radius" A_i,j​. Standing on this magic circle allows the agent to teleport to any cell within A_i,j​ steps, ignoring obstacles like water while moving, but they cannot teleport directly onto water cells.

User333 needs to determine whether they can reach the destination on each map using only flight and magic circles.

Input

The first line of input contains a positive integer T, representing the number of maps.

For each map, the input is structured as follows:

• The first line contains two positive integers N and M, representing the map's size N × M.

• The next N lines each contain M entries:

  A_1,1 , A_1,2 , ... , A_1,M
  ​A_2,1 , A_2,2 , ... , A_2,M
• Each entry A_i,j can be:
  • 'X' for water (impassable),
  • '0' for open grassland (passable),
  • An integer between '2' and '3' for a magic circle with that radius.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N,M ≤ 500
• A_i,j ∈ { 'X'  , '0' , '2' , '3' }
• Each map has at most 100 magic circles.
• The starting point (1,1) and the destination (N,M) are guaranteed to be open grassland.

Subtasks

• Testcases 1~2: N = 1, and there is no magic circle in the map.
• Testcases 3~4: N = 1
• Testcases 5~6: there is no magic circle in the map.
• Testcases 7~8: N,M ≤ 10
• Testcases 9~10: No additional restrictions.

 

Output

For each map, output a single line containing "YES" if it is possible to reach the destination from the start point, and "NO" otherwise (without quotes).

Please remember to print "\n" at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss