Safe Path in a Grid

You are given a grid of size \(n \times m\) consisting of the characters S (start), E (end), + (safety zone), . (empty cell) and # (obstacle). The task is to determine if there exists a path from S to E such that:

• The path takes at most \(k\) steps.
• The path passes through at least one safety zone +.

Movement is only allowed in the four cardinal directions (up, down, left, right) and you can only move onto cells that are not obstacles (i.e. not #).

If these conditions are met, output YES, otherwise output NO.

Note: A cell containing the safety zone + is counted only once regardless of how many times it is visited.

inputFormat

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

T
n m k
row1
row2
... 
rown
... (repeated for T test cases)

Here, T is the number of test cases. For each test case:

• n and m denote the dimensions of the grid.
• k is the maximum number of steps allowed.
• Next, there are n lines, each containing a string of length m representing a row of the grid.

The grid contains the characters S, E, +, ., and # with the meanings described above.

outputFormat

For each test case, print a single line on standard output containing YES if there exists a valid path from S to E satisfying the conditions, otherwise print NO.

## sample

2
4 4 5
S...
..+.
##.E
....
3 3 4
S#.
##+
..E

YES
NO

</p>