Run-up Jump

A grid has $N$ rows and $M$ columns. Each cell is either an empty cell or a trap. On this grid, a jump consists of a run-up followed by a long jump, in that order.

1. (Run-up) Choose an integer $x \ge 1$, pick one of the four directions (up, down, left, right) from the current cell, and move one cell at a time $x$ times in that direction. The moves must not enter a trap cell or leave the grid.
2. (Long jump) Then choose an integer $y$ with $0 \le y \le x + 1$, and jump $y$ cells in the same direction. The landing cell must not be a trap and must lie inside the grid.

Starting from the start cell, determine whether you can reach the end cell after any number of jumps.

The first line contains the number of test cases $T$ ($1 \le T \le 10\,000$).

Each test case follows.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 2\,000$).

Each of the next $N$ lines contains a string of length $M$ that describes one row of the grid. Each character is one of ., #, S, or E, with these meanings:

• .: empty cell
• #: trap
• S: start cell
• E: end cell

Each test case contains exactly one S and exactly one E.

The sum of $N \times M$ over all test cases is at most $4\,000\,000$.

For each test case, print one line. Print YES if you can reach the cell marked E, and NO otherwise.