E. Dark Matter Crisis
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The price of greed is awakening the nightmares slumbering in the abyss...

Explorer Little A has collected too many crystals in the Astra ruins, accidentally triggering the ancient self-destruct mechanism! The dark matter containers deep within the ruins have ruptured, and terrifying dark matter is beginning to spread outward.

The ruins can be viewed as an $$$N \times M$$$ 2D grid. The grid contains the following elements:

  • $$$\mathtt{A}$$$: Little A's current position (exactly one).
  • $$$\mathtt{E}$$$: The exit door of the ruins (exactly one).
  • $$$\mathtt{*}$$$: The source of ruptured dark matter (there may be none, or multiple).
  • $$$\mathtt{\#}$$$: Solid stone walls, which neither Little A nor the dark matter can pass through.
  • $$$\mathtt{.}$$$: Empty space.

Every $$$1$$$ second that passes, Little A can move to one adjacent cell in the four cardinal directions (up, down, left, right); simultaneously, each dark matter source will also spread to an adjacent cell in the four directions.

Extremely dangerous: Dark matter has the characteristic of instantaneous devouring. Little A must guarantee that at the exact moment he arrives at a certain cell, the dark matter has not yet spread to that cell. In other words, the time Little A takes to reach a cell must be strictly less than the time it takes for the dark matter to reach that cell. If the dark matter and Little A arrive at a cell at the exact same time, Little A will also be devoured!

Please help Little A calculate whether he can make it out alive to the exit door $$$\mathtt{E}$$$. If so, what is the minimum time (in seconds) required.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

For each test case: The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 1000$$$) — the number of rows and columns of the ruins grid.

The next $$$N$$$ lines each contain a string of length $$$M$$$, representing the map of the ruins. The characters in the string will only be $$$\mathtt{A}$$$, $$$\mathtt{E}$$$, $$$\mathtt{*}$$$, $$$\mathtt{\#}$$$, or $$$\mathtt{.}$$$.

It is guaranteed that the map contains exactly one $$$\mathtt{A}$$$ and exactly one $$$\mathtt{E}$$$.

It is guaranteed that the sum of $$$N \times M$$$ over all test cases does not exceed $$$2 \times 10^6$$$.

Output

For each test case, output a single integer on a new line.

If Little A can safely reach the exit, output the minimum time (in seconds) required.

If Little A will inevitably be devoured by dark matter, or if it is impossible to reach the exit at all, output $$$\mathtt{-1}$$$.

Example
Input
3
4 5
A....
..#..
..#..
*.#.E
4 4
A..*
....
....
...E
3 3
A#.
#.#
.*E
Output
7
-1
-1
Note

In the first example:

Little A is located at the top-left corner $$$(1, 1)$$$, the exit is at the bottom-right corner $$$(4, 5)$$$, and the dark matter source is at the bottom-left corner $$$(4, 1)$$$.

Little A's optimal route is to move right first and bypass the walls in the middle to reach the exit. Although the dark matter is spreading, Little A is fast enough to safely reach the exit at the $$$7$$$-th second.

In the second example:

The grid size is $$$4 \times 4$$$. Little A starts from the top-left corner, and the dark matter spreads from the top-right corner. Since the exit is at the bottom-right corner, no matter how Little A moves, the dark matter will arrive at the inevitable path near the exit before or at the same time as him. Little A is bound to be devoured, so the output is $$$-1$$$.

In the third example:

Little A is completely sealed in the top-left corner by walls. There is absolutely no path to the exit, so the output is directly $$$-1$$$.