소행성 지대

소행성 지대를 가로지르는 경로를 찾는다. 시작 위치, 최종 목적지, 그리고 소행성 지대의 생김새가 주어질 때, 어떤 소행성과도 부딪히지 않고 시작 위치에서 목적지까지 가는 최단 경로를 구하라.

소행성 지대는 $m \times m$ 크기의 문자 격자로 주어지며, 각 문자의 의미는 다음과 같다.

• s: 시작 위치
• d: 목적지
• -: 빈 공간
• *: 소행성

다음은 $4 \times 4$ 격자의 예시다.

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

우주선은 위, 아래, 왼쪽, 오른쪽으로만 이동할 수 있으며(대각선 이동 불가), 한 번의 이동은 인접한 빈 칸으로 한 칸 움직이는 것을 뜻한다.

첫 번째 줄에 데이터 세트의 개수를 나타내는 양의 정수 $n$이 주어진다. 각 데이터 세트의 첫 줄에는 정수 $m$이 주어지고, 이어서 $m$개의 줄에 걸쳐 각 줄마다 $m$개의 문자가 주어진다. 문자 s는 항상 왼쪽 위 모서리에, 문자 d는 항상 오른쪽 아래 모서리에 위치한다.

각 데이터 세트마다 목적지에 도달하기 위한 최소 이동 횟수를 출력한다. 도달할 수 없으면 -1을 출력한다.