로드 랠리

직사각형 격자 위에 놓인 경주 트랙을 생각해 봅시다.

소문자 x 또는 대문자 X는 벽이나 장애물을 나타냅니다. 각 숫자는 체크포인트를 나타냅니다. 오토바이는 체크포인트 0에서 출발하여 번호가 매겨진 모든 체크포인트를 번호가 커지는 순서대로 방문해야 하며, 가장 큰 번호의 체크포인트에서 코스를 끝냅니다.

오토바이는 다음과 같이 관성을 가지고 움직입니다. 첫 번째 초에는 반드시 출발 칸의 8개 이웃 칸 중 하나로 이동해야 합니다. 그 이후의 매 초마다, 직전 이동에서의 가로·세로 이동량을 그대로 한 번 더 반복하여 도달하는 칸을 $P$라고 할 때, 오토바이는 $P$ 또는 $P$의 8개 이웃 칸 중 하나로 이동할 수 있습니다. 즉, 속도의 각 성분은 1초에 최대 1만큼만 변할 수 있습니다. 오토바이는 격자 밖이나 x/X 칸에 착지할 수 없지만, 빈 칸이나 체크포인트에 착지하기만 한다면 하나 이상의 벽을 뛰어넘는 것은 허용됩니다.

예를 들어 위 배치에서 라이더는 a, b, c, … 로 표시된 칸의 순서를 따라 이동하여

6초 만에 첫 번째 체크포인트에 도달할 수 있습니다.

0에서 출발하여 마지막 체크포인트에서 끝나되, 중간의 각 체크포인트를 숫자가 가리키는 순서대로 착지하며 방문하는 데 필요한 최소 시간을 구하는 프로그램을 작성하세요. 오토바이는 다른 곳으로 가는 도중에 순서에 맞지 않는 체크포인트 위를 지나갈 수 있지만, 더 작은 번호의 체크포인트를 모두 방문한 뒤에야 그 체크포인트를 방문한 것으로 인정됩니다.

입력은 여러 개의 경주 코스로 이루어집니다. 각 코스는 트랙의 너비 $w$와 높이 $h$를 나타내는 두 정수가 담긴 한 줄로 시작하며, $1 \le w \le 40$, $1 \le h \le 40$입니다. 0 0으로 이루어진 줄은 입력의 끝을 의미합니다.

그다음에는 정확히 $w$개의 문자로 이루어진 $h$개의 줄이 이어지며, 위에서 설명한 대로 트랙을 정의합니다. 모든 트랙의 넓이는 2 이상이고, 최소 두 개(0과 1)에서 최대 10개의 체크포인트를 포함합니다. 체크포인트가 두 개보다 많은 경우, 번호는 빠짐없이 연속됩니다.

각 코스마다 코스를 완료하는 데 필요한 최소 시간(초)을 정수로 한 줄에 하나씩 출력하세요. 코스를 완료할 수 없는 경우에는 대신 -1을 출력하세요.