명탐정 준하

명탐정 준하에게 미술품 절도 사건의 수사 의뢰가 들어왔다. 여러 미술관에서 작품이 연달아 도난당한 사건이다. 왕년에 화가로 활동했던 준하는 이 소식을 안타깝게 여겨 곧바로 사건을 맡기로 했다.

도난이 일어난 일대는 4행 5열 격자 지도로 나타낸다. 지금까지 확보한 단서는 범인이 처음 출발한 칸, 도난당한 미술관의 칸과 도난이 일어난 순서, 범인의 흔적이 발견된 칸이다. 준하는 수학적 머리와 예술적 감각을 발휘해 범인의 행동 규칙을 다음과 같이 확신했다.

• 범인은 한 번에 상하좌우 중 한 방향으로 한 칸 이동한다. 지도 밖으로 나가지는 않는다.
• 아직 들어간 적 없는 미술관 칸에 도착하면 곧바로 그 미술관에 들어가 작품을 훔친다. 그래서 미술관에는 도난이 일어난 순서대로만 들어간다. 1번 미술관을 방문하기 전에 2번이나 3번 미술관 칸으로 이동하는 것은 불가능하다.
• 범인이 지나간 칸에는 반드시 흔적이 남는다. 그러므로 흔적이 없는 칸은 범인이 한 번도 지나가지 않았고, 흔적이 발견된 칸은 범인이 적어도 한 번 지나갔다. 같은 칸을 여러 번 지나는 것은 가능하다.

준하를 도와 범인이 이동한 최단 거리를 구하자.

입력은 여러 테스트케이스로 이루어진다. 첫째 줄에 테스트케이스의 개수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트케이스는 4개의 줄로 이루어지고, 각 줄에는 길이가 5인 문자열이 주어진다. 각 문자의 뜻은 다음과 같다.

• 0: 범인이 처음 출발한 칸
• 1 이상의 수: 도난당한 미술관 칸이며, 그 수가 도난이 일어난 순서다. 9보다 큰 수는 A부터 시작하는 대문자 알파벳으로 적는다. 10은 A, 11은 B이다.
• #: 범인의 흔적이 발견된 칸
• .: 사건과 관련이 없는 칸

0은 정확히 한 번 등장한다. 미술관의 번호는 1부터 빠짐없이 이어지고, 같은 번호가 두 번 이상 등장하지 않는다. 지도의 칸이 20개이므로 미술관은 많아야 19곳이고 가장 큰 번호는 J이다. 테스트케이스 사이는 빈 줄로 구분한다.

테스트케이스마다 범인이 이동한 최단 거리를 한 줄에 하나씩 출력한다. 이동 거리는 범인이 칸을 옮긴 횟수이고, 출발 칸에서 한 번도 움직이지 않았다면 0이다.

범인은 .이 아닌 모든 칸, 즉 출발 칸과 모든 미술관 칸과 흔적이 남은 모든 칸을 적어도 한 번 지나야 한다. 이미 지난 칸은 몇 번이든 다시 지나도 되지만, 미술관에 처음 들어가는 순서는 도난이 일어난 순서를 따라야 한다.

조건을 만족하는 이동이 존재하지 않으면 -1을 출력한다.