Haunted House (part 1)

Note: This problem statement is identical to Haunted House (part 2), but does not include the magical bell.

You’re in a haunted house with corridors and walls. Your goal is to get from S (start) to E (exit) while avoiding ghosts that roam the house.

The house is an $N \times M$ grid:

'S' — your starting cell (exactly one).
'E' — the exit (exactly one).
'.' — empty floor (you can walk here).
'X' — wall (you cannot enter).

There are $K$ ghosts. Each ghost starts at some given cell (r, c) and moves in one of the four directions (up, down, left, right), without ever changing course.

Ghosts can do a lot of stuff that you can't. Specifically, ghosts ignore inner walls (they can pass through 'X'). Also, when they reach an outer wall, they wrap around the corresponding row or column:

A ghost moving up from row 0 goes to row N-1.
A ghost moving down from row N-1 goes to row 0.
A ghost moving left from col 0 goes to col M-1.
A ghost moving right from col M-1 goes to col 0.

All ghosts move one cell per second, simultaneously. You also move one cell per second (up, down, left, right), or you may wait in place.

There are two ways to collide with a ghost:

If at the end of a second, you and the ghost occupy the same cell.
If you pass through a ghost (you move A→B while the ghost moves B→A).

Your task: find the minimum time (in seconds) to reach E from S without ever colliding with a ghost.

Input

The first line contains an integer $T$ — the number of test cases.

For each test case:

A line with three integers $N, M, K$ ( $2 \leq N, M \leq 30$ , $1 \leq K \leq 50$ ).
$N$ lines of length $M$ describing the house with characters from {S, E, ., X}.
All characters are uppercase; S and E appear exactly once; S and E are not on walls.
$K$ lines with ghost info: r c d
- $0 \leq r < N$ , $0 \leq c < M$
- $d \in U, D, L, R$
- No ghost will start where S is located.

Test cases will be separated by a ===== string.

Output

For each test case, print a single line Case #i: t, where t is the minimum number of seconds to reach E from S without collision, or -1 if it’s impossible.

Example

Input

4
3 3 1
S..
.X.
..E
1 2 D
=====
4 5 2
S...E
.XXX.
.....
....X
0 2 L
2 3 L
=====
4 5 2
S...E
.XXX.
.....
....X
0 2 L
2 2 L
=====
3 4 1
S...
XXXX
...E
2 0 U

Output

Case #1: 5
Case #2: 10
Case #3: 14
Case #4: -1

Explanation

Case 1. One of the optimal ways to get to the exit is to move 2 cells down, wait for a second, and move two cells right. Here is the corresponding state of the haunted house (@ denotes your position, G denotes the ghost):

t = 0	t = 1	t = 2	t = 3	t = 4	t = 5 (finish)
@.. .XG ..E	... @X. ..G	..G .X. @.E	... .XG @.E	... .X. .@G	..G .X. ..@

Note how at second 5, you move into the exit cell just as the ghost leaves it to wrap around to the top row. Also note that you could wait for 1 second at any point on this path (i.e., not necessarily after 2 seconds).

Case 2. The ghosts are positioned as follows:

S.G.E
.XXX.
...G.
....X

You cannot reach the exit by moving right, as the ghost in row 0 blocks the path. You also cannot go straight through row 2, because you'd collide with the ghost in that row. The optimal path can be seen here:

@...@
@XXX@
@..@@
@@@@X

Case 3. This is the same haunted house as in Case 2, but this time the ghost in row 2 starts in a different spot:

S.G.E
.XXX.
..G..
....X

The optimal path still looks the same as in the previous test case, but you need to wait 4 extra seconds on the way to avoid colliding with the ghosts, for a total of 14 seconds.

Case 4. There is no path from the start cell to the end cell.