Illidan Stormage, the blind Warcraft hero is thrown in a maze for punishment. Being a blind hero, he cannot see anything but he can sense which direction is North, East, South and West.

Assume that the maze is laid out on a grid, and each grid location is either blocked or free or contains a demon. He has four possible moves: North, East, South, and West. Illidan starts from a free location at time t = 0, and his goal is to kill all the demons within time T. Illidan kills a demon immediately (takes 0 unit of time) whenever he lands on a grid location containing a demon, however making a move to an adjacent cell takes exactly 1 unit of time. If Illidan attempts to move out of the grid or attempts to move to an obstacle, he will stay in his current location but it will still cost him 1 unit of time. When Illidan kills the last demon, he is immediately freed from the maze but if he fails to kill all the demons within time T, he will be trapped in the maze for eternity.

Keep in mind that Illidan is blind, so he may get confused while making a move. To avoid all this chaos, he decides to follow a rather simple strategy. Before he starts his journey to hunt and kill all the demons, he selects four real numbers: P_N, P_E, P_S and P_W denoting the probability to move North, East, South and West respectively. No matter where he is, he will always attempt to move North with probability P_N, East with probability P_E, South with probability P_S, and West with probability P_W.

Given the description of the maze, the location of all the demons, Illidan's starting position and the probabilities of each move, calculate the probability that Illidan will be able to kill all the demons before the time runs out.

Assume the grid will be of dimensions N x M and will contain K demons.

Input

The first line of the input contains an integer Q, denoting the number of test cases. Then the description of Q test cases follow. The first line of every test case will be a blank line.

The second line contains three space separated integers, N, M and T, denoting the number of rows, the number of columns of the grid and the time by which Illidan needs to kill all the demons respectively. The third line contains four space separated real numbers P_N, P_E, P_S and P_W in that order. All these numbers will contain at most 2 digits after the decimal point.

Each of the next N lines will contain exactly M characters on each line describing the grid. The grid will only consist of the characters . @ # and *.

• . indicates a free cell.
• @ indicates Illidan's starting position which is also a free cell and will occur exactly once.
• # denotes an obstacle.
• * denotes the location of a demon, there can be at most one demon in a cell.

Constraints

• 1 ≤ Q ≤ 5
• 1 ≤ N, M ≤ 8
• 1 ≤ T ≤ 16777216
• 1 ≤ K ≤ 3
• P_N + P_E + P_S + P_W = 1

Output

For each test case, print the probability of Illidan escaping the maze in a single line. Error less than 10^-6 will be ignored.

Example

Input:
3

1 2 3
0 0.5 0 0.5
@*

1 8 64
0 0.5 0 0.5
@......*

8 8 10000000
0.05 0.25 0.45 0.25
##....#.
.##.....
.*#.##..
.##..*#.
...###..
.#.#....
.#.#.#..
@#.*.#..


Output:
0.875000000000
0.693211582717
0.157323987423

Credits

Problem name and story inspired by LightOJ 1426 - Blind Escape.

Or if you prefer a not so blind version SPOJ NBLINDESC- Not So Blind Escape.

---

hide comments

	:D: 2019-11-25 20:54:39 Phenomenal problem. Pretty difficult. Had to redo my first solution attempt, but it was very fun finding and implementing the second one. The problems description is also high quality. Thanks for setting it up sgtlaugh. Now if I could just figure out how to get sub 1s :) -> This problem can be solved in multiple ways. Thanks for the kind words :D You can try another related problem as well now. https://www.spoj.com/problems/NBLINDESC/ Last edit: 2019-12-20 17:02:19
	[Rampage] Blue.Mary: 2019-11-15 02:17:31 Is there any special constraint on parameter K? -> Of course. Sorry I mistakenly omitted it. Please check now. Last edit: 2019-11-16 03:53:12