Asteroid Field

Interview

Time limit1sMemory limit128 MB

Summary

Find the minimum number of moves from the top-left cell to the bottom-right cell in a grid, avoiding asteroid cells.

Level: Easy3 of 10
Topics: BFS, Graph, Matrix
Solved: No attempts yet

Problem

Plot a path through an asteroid field. Given a starting location, a final destination, and a description of the asteroid field, find a shortest path that takes you from the start to the destination without hitting any asteroid.

The asteroid field is described by an $m \times m$ grid of characters, where each character means:

s: starting location
d: destination
-: open space
*: asteroid

Here is an example of a $4 \times 4$ grid.

s*-*
-*-*
----
*-*d

Your ship can move up, down, left, and right (not diagonally). One move takes the ship one step into an adjacent open cell.

Input

The first line contains a positive integer $n$ , the number of data sets. The first line of each data set contains an integer $m$ , followed by $m$ lines that each contain $m$ characters. The character s is always in the top-left corner and d is always in the bottom-right corner.

Output

For each data set, print the minimum number of moves needed to reach the destination, or -1 if it is unreachable.

Examples1

Example 1

Input

2
4
s*-*
-*-*
--*-
*-*d
6
s*---*
-*-*--
---**-
***---
--*-**
*-*--d

Expected output

-1
18