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