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 N x M grid, and each grid location is either blocked or free. Illidan starts from a free location at time 0, and his goal is to escape from the maze. He has four possible moves - move to North, East, South or West. 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 into an obstacle, he will stay in his current location but it will still cost him 1 unit of time. There is exactly one exit in the maze, located in one of the free cells. Illidan escapes immediately whenever he reaches the exit.

Keep in mind that Illidan is blind, so he may get confused while making a move. To avoid all this chaos, he decided to follow a rather simple strategy. Before he starts his journey to escape the maze, 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. At any moment, Illidan must attempt to make a move in one of these four directions. In other words, this means that P_N + P_E + P_S + P_W = 1.

Illidan does not want to be stuck in the maze for too long. He has information about the maze so he knows his starting position, the location of the exit cell and all the free cells and obstacles initially. Before he attempts to escape, he would like to set the values P_N, P_E, P_S and P_W such that the expected time for him to escape the maze is minimized.

Given the description of the maze, Illidan’s starting position and the location of the exit cell, calculate the minimum expected time for Illidan to escape. You can safely assume that Ilidan’s starting cell and the exit cell will always be connected, that is, it will be possible to reach the exit cell via some sequence of moves.

Input

The first line of the input contains an integer T, denoting the number of test cases. Then the description of T test cases follow. The first line of every test case will start with a blank line. The second line contains two space separated integers, N and M denoting the number of rows and the number of columns of the grid. 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 the exit cell, is of course a free cell and will occur exactly once.

Constraints

1 ≤ T ≤ 32

1 ≤ N, M ≤ 8

Output

For each test case, print the expected time for Illidan to escape the maze if he chooses the probabilities optimally in a single line. Absolute error less than 10^-6 will be ignored.

Sample Input

2

1 2
@*

3 3
@..
#.#
..*

Sample Output

1.0000000000000
16.360252929211

Credits

Problem name and story inspired by LightOJ 1426 - Blind Escape

Or if you prefer a blinder (easier) version SPOJ BLINDESC - Blind Escape II

---

hide comments

	Viplov Jain: 2023-05-05 22:03:02 @sgtlaugh: Can you check my submission, is it an error bound issue or something else? Never mind, got it (was a numerical error) Last edit: 2023-05-06 03:59:09
	suhash: 2020-06-19 15:39:22 sgtlaugh@: Could you tell me if my latest submission only has precision errors or is it failing for some cases? [EDIT] nvm: I think I found some issues with my code. [EDIT]: Solved finally (had precision issues handling very small values). Really nice problem! Thanks for setting it up @sgtlaugh :) -> Sorry I just noticed your comments. Good to see that you've finally solved it, congratulations! Did the tags help or was it intuitive? :) The first part was intuitive since I've solved similar problems before (for e.g. https://www.spoj.com/problems/AVMG2/). The hill climbing tag definitely helped as it led me to examine the nature of the probability distribution and understand the shape of the function. Really great problem. :) -> Wow! Thanks for solving it and the comment! Last edit: 2020-06-22 19:56:47
	[Rampage] Blue.Mary: 2019-11-18 04:29:44 Is the error bound actually absolute or relative? -> Good question! In the onsite contest, it was either absolute or relative. Since the answer can't be less than 1, it was relative. Here, I used the generic judge which will ignore FP rounding up to 10^-6. I'm not exactly sure if that uses absolute or relative error, but looks like it only checks for absolute error. Btw, do you think it'd be better to relax the precision error more? I see that you got quite a few wrong answers before finally getting accepted. -> I've done several tests after I get AC. The largest answer I can get is about 3e3. If you use judge "Ignore FP Rounding up to 1e-6", the actually relative error bound is about 3e-10. This is somewhat tight when using double. (When I solve problems in other OJs, usually they use relative error bound 1e-6 or 1e-9.) -> It is a bit strict indeed, but still doable with doubles. And you're right about the observation, I couldn't generate any input where the answer exceeds 4000. I'll write a special judge and rejudge all submissions once I can find some time to make it more lenient. Last edit: 2020-02-16 21:05:00