For Mactoberfest, Mackenzie has decided to set up a maize maze for everyone to try and solve. Alex's teacher has just taken the class to try it out and the students quickly raced to solve the maze. However, Alex has realized that the longer he spends in the maze, the more class time he gets to skip!

The maze is set up as an grid of either walls (marked with `#`

) or places he can
walk (marked with `.`

). Alex wants to take as long as he can to find his way out, however
he needs to be careful. If his teacher catches him walking in circles, then she will
suspend him! Obviously, Alex would hate being forced to skip school, so he won't visit
any location more than once. Help Alex figure out the length of the longest path that he
can take to exit the maze.

#### Input Specification

The first line of input provides the number of test cases, . test cases
follow. Each test case starts with an integer . lines follow, each
containing characters, which describe the maze. A character is either `.`

(place Alex
can walk), `#`

(wall), `A`

(Alex's starting location), or `E`

(the exit).

#### Output Specification

For each test case, your program should output the length of the longest path that Alex can take to the exit.

#### Sample Input

```
3
4
A...
.##.
....
...E
5
A....
.....
###..
E##..
.....
5
E...#
##..#
###.#
##A.#
.....
```

#### Sample Output

```
12
19
9
```

#### Explanation for Sample

The paths are outlined with numbers modulo 10 below:

```
A123
.##4
8765
901E
A3478
12569
###10
E##23
87654
E87.#
##65#
###4#
##A3#
..12.
```

## Comments