시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 60 10 6 15.789%

문제

명탐정 준하에게 범인 수색의 의뢰가 맡겨졌다. 얼마 전 여러 미술관에서 미술 작품이 도난당한 사건이 있었는데, 그 범인을 찾는 의뢰였다. 왕년에 화가로 활동했던 준하는 이 사실이 안타까워 바로 사건을 담당하기로 하였다. 지금까지 알려진 단서는 범인이 가장 처음에 목격된 장소와 도난당한 미술관의 장소 및 도난당한 순서, 마지막으로 범인의 흔적이 발견된 장소들이다. 이 장소들은 4 * 5크기의 2차원 격자로 된 지도로 나타낼 수 있다. 또한 현재 장소에서 상, 하, 좌, 우로 한 칸씩만 이동할 수 있다.

준하는 우선 범인이 처음 목격된 장소로부터 범인의 이동 경로를 조사해보기로 하였다. 준하의 수학적 두뇌와 예술적 감각에 의하면 범인은 자신이 잘 알고 있는 사람일 가능성이 높으며, 그 사람은 지금까지 발견된 모든 장소를 최소의 거리로 움직였음이 틀림없다고 생각하였다. 또한, 범인은 일부러 흔적을 남겼고, 따라서 다른 장소는 방문하지 않았다고 확신하였다. 준하를 도와 범인의 최소 이동 거리를 구해주자.

입력

입력은 여러 테스트케이스로 이루어져 있다. 첫째 줄엔 테스트케이스의 개수 T가 주어진다. (1≤T≤10)

각 테스트케이스마다 첫째 줄부터 4줄에 걸쳐 4 * 5 크기의 지도가 입력으로 주어진다. 지도에서 숫자 0은 범인이 처음 목격된 장소이며, 1부터 이어지는 나머지 숫자는 도난당한 미술관의 장소를 의미한다. 9보다 큰 숫자는 A부터 시작하는 알파벳으로 표시한다. 도난당한 순서는 숫자의 크기가 작은 순서이다. #은 범인의 흔적이 발견된 장소이며 ‘.’은 아무 연관이 없는 장소를 의미한다. 각 테스트케이스끼리는 빈 줄로 구분이 되어있다.

출력

테스트케이스마다 한 줄씩 범인의 최소 이동 거리를 출력한다.

범인은 왔던 길을 다시 방문할 수 있지만, 미술관에 처음 방문할 때는 도난이 발생한 순서를 따라야 한다.

만약 범인의 이동이 불가능한 경우는 -1을 출력한다.

예제 입력

2
##2##
#.0.#
3.#.#
##1##

##2##
#.0.#
#.3.#
##1##

예제 출력

15
-1

힌트