Children of the Candy Corn

A cornfield maze is a popular Halloween attraction. Visitors enter at the marked entrance and wander through the maze until they reach the exit.

One well-known strategy is guaranteed to lead a visitor out of the maze eventually: put one hand on a wall (either the left wall or the right wall) and keep following that same wall, never lifting your hand. Neither choice (left or right) is always better, and the resulting route is rarely the most efficient one. (This method fails on mazes whose exit is not on an outer edge, but no such maze appears in this problem.)

As the owner of a cornfield that is about to be turned into a maze, you want a program that, for a given layout, reports the length of the left-hand route, the length of the right-hand route, and the length of the shortest route, so you can judge which layout is most likely to confuse visitors.

While following a wall you always move to an adjacent open square in the horizontal or vertical direction; diagonal movement is not allowed. You begin at the entrance facing into the maze, and you stop the moment you reach the exit.

The first line contains a single integer $n$, the number of mazes.

Each maze begins with a line containing its width $w$ and height $h$ ($3 \le w, h \le 40$), followed by $h$ lines of exactly $w$ characters describing the layout:

• # is a wall,
• . is an open square,
• S is the start (entrance),
• E is the exit.

Each maze contains exactly one S and one E. Both lie on an outer edge of the maze but never in a corner, and they are separated by at least one wall. The maze is completely enclosed by walls, with S and E as the only openings. The exit is always reachable from the start.

For each maze, print one line with three integers separated by single spaces: the number of squares visited (counting S and E, and counting repeated visits) by the left-hand route, then the right-hand route, then the shortest route, in that order. Movement is allowed only horizontally or vertically, never diagonally.