#1966 테세우스

33  1 s   128 MB  

Description

나는 테세우스. 미노타우로스를 잡으러 미궁에 들어왔징 우왕ㅋ굳ㅋ.

근데 나 말이야, 바람피다 걸려서 아리아드네가 실을 태워버렸쩡 ㅜㅠ

못 나갈 것 같아 여기. ㅜㅜ

나의 용사여.. 나 좀 도와주지 않을랭? 그리고 나 좀 급해서..  최대한 빨리 나가고 싶어 ㅜㅠ

지도를 알려줄테니 얼마나 참으면 되는지 알려주랑 ㅜㅠ

그럼 부탁해요 캡틴

Input

입력의 첫줄에 테스트 케이스 갯수가 들어온다

다음 줄에 지도의 크기 N( 2 <= N <= 1000 )이 들어온다

그 뒤에 NxN 의 지도가 주어진다.

돌덩이로 막힌 곳은 X, 지뢰가 있는 곳은 @, 지나 갈 수 있는 곳은 O로 주어진다.

테세우스의 위치는 항상 O로 주어진다.

Output

각 테스트케이스마다 테세우스가 출구로 갈 수 있는 최소 걸음 수를 출력한다. (걸음 = 현재 칸에서 인접한 다른 칸으로 움직임)

테세우스의 좌표는 항상 (1,1) (좌측상단을 1,1로 기준으로 한다) 이며, 출구의 좌표는 (N,N) 이다.

테세우스가 나갈 수 없는경우 (물론 불쌍하지만) 때는 불쌍하니 pitty! 라고 출력한다

Sample Input

Sample Output

1
3
O@@
OO@
XOX
pitty!