You will be given a grid of size N * M. The character of grid is either ‘.’ Or ‘#’. '.' means free location and '#' means a fire. Q sequence of moves are given as string of character ‘N’, ’S’, ’E’, ’W’. You are at point ( Xstatrt, Ystart ), and want to reach ( Xend, Yend ). At any point you can,
• Choose any one sequence out of Q sequences.
• If you start any sequence, you have to finish that sequence.
• If choosing a sequence X, (1<=X<=Q) take you to the fire or outside of grid then you will die. You can die at the end of the sequence X or in middle of that sequence.
• Cost of the chosen sequence is length of that sequence.
• ‘N’ moves 1 cell to north, ‘S’ moves 1 cell to south, ‘E’ moves 1 cell to east, and ‘W’ moves 1 cell to west.
You have to print minimum cost of moving from starting point to destination point. If it is not possible to reach to destination print -1.
Input
First line of input will consist of an integer T (T<=41), indicates the number of test cases follow. Each case starts with a line containing two integers M and N (1 ≤ M, N ≤ 40) denoting the number of rows and columns of the grid respectively. Each of the next M lines contains N characters (either '.' or '#') denoting the maze. '.' means free location and '#' means a fire. Next line consist of an integer Q, (1<=Q<=40) denoting the number sequence of moves. Next Q lines contains nonempty string S, Such that 1<=|S|<=40 and string is composed of only four characters described above. Next line contains two integers indicates starting location. Last line contains two integers indicated destination location. It is guaranteed that starting and ending location are always within grid and does not contains fire.
Output
For each test case you have to print the required answer.
Sample
| Input | Output |
|---|---|
1 3 3 .#. ..# ... 4 SS EE ESE S 1 1 3 3 | 4 |
If your position is (x, y) then, ‘N’ moves 1 cell to north (x-1, y), ‘S’ moves 1 cell to south(x+1, y), ‘E’ moves 1 cell to east(x, y+1), and ‘W’ moves 1 cell to west(x, y-1)
