파이프

사무용 건물을 짓는 일은 매우 표준화되었다. 미리 제작된 모듈을 고객의 요구에 맞게 조합하고, 멀리 떨어진 공장에서 실어 와 현장에서 조립한다. 그래도 여전히 세심한 계획이 필요한 작업이 있는데, 그중 하나가 난방 배관을 어떻게 놓을지 정하는 일이다.

현대식 사무용 건물은 정사각형 모듈들로 이루어진다. 각 층에는 서비스 모듈이 정확히 하나 있으며, 이 모듈에서 (여러 가지 중에서도) 난방 배관을 통해 나머지 모듈들로 온수를 내보낸다. 서비스 모듈을 포함한 모든 모듈은 이웃한 두 개에서 네 개의 모듈 중 정확히 두 개와 난방 배관으로 연결된다. 따라서 배관은 서비스 모듈에서 출발하여 모든 모듈을 정확히 한 번씩 지난 뒤 다시 서비스 모듈로 돌아오는 하나의 폐회로를 이룬다.

모듈마다 성질이 달라, 인접한 두 모듈을 연결하는 비용도 서로 다르다. 예를 들어 두 모듈 사이에 두꺼운 벽이 있으면 배관을 놓는 비용이 커진다. 한 층의 정보가 주어질 때, 난방 배관을 놓는 가장 저렴한 방법을 구하라.

첫 줄에는 처리할 층의 수를 나타내는 정수 하나가 주어진다. 이어서 그 수만큼의 층 정보가 주어진다.

각 층 정보는 새 줄에서 두 정수 $2 \le r \le 10$ 과 $2 \le c \le 10$ 으로 시작하며, 층의 크기는 $r$ 행 $c$ 열의 모듈이다. 다음 $2r + 1$ 개의 줄에 층이 ASCII로 그려지며, 각 줄은 $2c + 1$ 개의 문자로 이루어진다.

이 그림에서 바깥 경계는 # 로 그려지고, 각 모듈의 중심은 공백이다. 인접한 두 모듈을 나누는 내부 벽은 하나의 숫자 0–9 로, 그 벽을 통해 배관을 놓는 비용을 뜻한다. 모든 층은 완전한 직사각형이며 모듈 수는 항상 짝수이다.

각 층마다 가장 저렴한 경로의 비용을 한 줄에 출력한다.