Escape

You are trapped in a large rectangular room paved with big square tiles. Some tiles are open, others are blocked by obstacles or walls. One step takes you to a tile that touches your tile horizontally or vertically, so diagonal moves are not allowed.

To shake off anyone following you, you refuse to walk in a straight line. You take a turn at every opportunity and never keep one direction longer than strictly necessary. For example, if you enter a tile from the south, you turn left or right and leave to the west or the east. Only when both of those sides are blocked do you carry straight on. You never turn around and go back the way you came.

At the start there is no direction behind you, so you may take your first step toward any open neighbour of the starting tile.

You escape the moment you stand on a tile at the edge of the room, meaning a tile in the first row, the last row, the first column or the last column. Given a map of the room and your starting tile, work out how many steps the escape takes.

The first line contains an integer $t$ ($1 \le t \le 100$), the number of test cases. Each test case is given as follows.

• A line with two integers $h$ and $w$ ($1 \le h, w \le 80$) separated by a space, the height and the width of the room.
• Then $h$ lines, each with $w$ characters, describing the room. Each character is . for an open space, # for a blocked space, or @ for your starting location. Every room description contains exactly one @.

For each test case print one line with the minimal number of steps needed to reach the edge of the room, or -1 if no escape is possible.