Kibid is a system engineer at the Faculty of Computer Science and Engineering. Today, he is responsible for the organization of the ACM competition in informatics. Unfortunately for everyone, Kibid isn't a very good engineer, so don't be surprised if there are some problems during the competition. If, however, something goes wrong, Kibid knows that he would be the first one that people will point the finger to, so he wants to know how quickly he can escape - if that is necessary.

The faculty building can be represented as a rectangular grid, where each cell is marked with either '.' (free cell), 'X' ('impassible/broken cell), 'S' (start cell), or 'E' (exit cell). There could be more than one exit cell, and there will always be a path from the start cell, to at least one exit.

Kibid doesn't know the building all that well, since he rarely actually does any work done. So, when he will escape, he will randomly walk between cells - that is, from the cell that he is currently at, he will randomly choose a passable cell ('S', '.' or 'E') that is a neighbor of the current cell, and move there (continuing this algorithm until he lands on an exit). If you know how the building looks, can you help Kibid calculate the expected number of moves required to escape?

Note: Two cells are neighbors if they share an edge - either horizontally or vertically.

Input

The first line of input contains one positive integer T (1 <= T <= 20), the number of test cases.

The first line of every test case starts with two numbers R and C (1 <= R, C <= 12), the number of rows and the number of columns of the rectangular grid describing the faculty building.

Each of the next R lines contain C characters each ('.', 'X', 'S' or 'E'). There will be exactly one start cell 'S', and at least one exit cell 'E'.

Output

For each test case, on a separate line, output the expected number of moves (with 10 decimal places). Your solution will be considered correct if it is within an absolute or relative error of 10^-7 of the correct answer.

Constraints

Time limit: 5 seconds
Memory limit: 64 megabytes

Examples

input
2
2 2
S.
.E
4 1
E
.
.
S

output
4.0000000000
9.0000000000