석유 탐사

석유를 시추하려면 먼저 석유가 어디에 있는지 찾아야 합니다. 석유 회사는 가능한 한 저렴하게 뽑아낼 수 있는 석유를 찾으려 합니다. 가격을 결정하는 큰 요소 중 하나는 석유에 도달하기까지 얼마나 깊이, 그리고 어떤 물질을 뚫고 내려가야 하는가입니다. 이 문제에서는 석유 매장량의 크기는 고려하지 않습니다. 해저 지형도가 주어질 때, 여러 지점에서 시추하는 데 드는 비용을 계산하세요.

첫째 줄에 데이터 집합의 개수 $K$가 주어집니다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어집니다.

각 데이터 집합의 첫째 줄에는 두 정수 $h$와 $w$ ($1 \le h, w \le 40$)가 주어집니다. 각각 해저 지형도의 높이와 너비입니다. 그 다음 $h$개의 줄이 주어지며, 각 줄은 $w$개의 대문자로 이루어진 문자열입니다. 각 문자는 다음 중 하나입니다.

• X: 그 위치에 석유가 있음
• H: 단단한 암석
• S: 무른 암석

단단한 암석은 한 칸을 뚫는 데 $3$의 비용이 들고, 무른 암석은 한 칸을 뚫는 데 $1$의 비용이 듭니다. 각 열마다 맨 위에서 아래로 수직으로 내려가며 처음 석유를 만날 때까지 뚫는 총비용을 구하세요. 어떤 열에서는 석유를 전혀 만나지 못할 수도 있으며, 이때는 비용 대신 문자 N을 출력합니다.

각 데이터 집합에 대해 먼저 Data Set x: 형식의 줄을 출력합니다. 여기서 $x$는 데이터 집합의 번호입니다(1부터 시작). 다음 줄에는 왼쪽에서 오른쪽 순서로 $w$개 열의 시추 비용을 공백 하나로 구분하여 출력합니다(줄 끝에 공백을 두지 않습니다). 석유가 없는 열에는 N을 출력합니다. 연속한 두 데이터 집합의 출력 사이에는 빈 줄을 하나 넣습니다(마지막 데이터 집합 뒤에는 빈 줄을 두지 않습니다).