Word Search in a 2D Grid

Given a 2D grid of characters of size \(N \times M\), determine whether a specified word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells include those horizontally, vertically, or diagonally neighboring. Each cell can be used at most once in forming the word.

This problem tests your ability to perform depth-first search with backtracking in a grid.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer \(T\), the number of test cases.
2. For each test case:
   1. A line with two integers \(N\) and \(M\) representing the numbers of rows and columns of the grid.
   2. Next \(N\) lines, each containing a string of exactly \(M\) uppercase letters (without spaces), representing the grid.
   3. A line containing a string which is the target word.

outputFormat

For each test case, print a line to stdout containing either YES if the word exists in the grid, or NO if it does not.

## sample

2
3 4
ABCE
SFCS
ADEE
ABCCED
3 4
ABCE
SFCS
ADEE
ABCB

YES
NO

</p>