Domiyahtzee!

야찌는 주사위 다섯 개로 여러 조합을 만들어 점수를 얻는 게임이다. Domiyahtzee의 점수표는 아래와 같다. 앞의 두 조합은 야찌의 공식 규칙과 조금 다르다.

Domiyahtzee는 $5 \times 5$ 격자에서 한다. 도미노 한 벌은 1부터 6까지의 눈을 두 개씩 짝지은 21개로, (1,1), (1,2), ..., (1,6), (2,2), (2,3), ..., (6,6)이 각각 한 개씩 있다. 격자에는 이 21개 중 12개를 놓고, 남은 한 칸에 1 이상 6 이하의 값 하나를 놓는다. 이 값 하나를 싱글턴이라고 한다. 그래서 25칸에 숫자가 하나씩 적혀 있다.

격자에는 선이 12개 있다. 가로 5줄, 세로 5줄, 긴 대각선 2개다. 선 하나가 주사위 다섯 개에 해당한다. 한 선은 그 선에 있는 조합 중 점수가 가장 높은 조합 하나만 점수로 얻고, 아무 조합도 없으면 0점이다. 예를 들어 눈이 6 5 5 6 6인 선에는 18점인 3-of-a-Kind와 25점인 Full House가 있고, 이 선의 점수는 25점이다.

Yahtzee는 격자 전체에서 함께 센다. Yahtzee인 선이 $k$개이면($k \ge 1$) 그중 하나가 50점, 나머지 $k - 1$개가 각각 100점이다. 격자의 점수는 선 12개의 점수를 모두 더한 값이다.

도미노 하나를 최대 한 번 바꿔서 점수를 올릴 수 있다. 격자에 놓인 도미노 하나를 골라 치우고, 격자에 없는 도미노 9개 중 하나를 빈 두 칸에 놓는다. 새 도미노는 치운 도미노가 쓰던 두 칸을 그대로 쓰고, 어느 쪽 눈을 어느 칸에 놓을지는 마음대로 정한다. 싱글턴은 옮기지 않는다. 격자를 그대로 두어도 된다.

이렇게 얻을 수 있는 가장 높은 점수를 구하라.

첫 줄에 격자의 개수 $n$이 주어진다. ($1 \le n \le 100$)

격자 하나는 명세 13개로 주어진다. 각 명세는 H a b, V a b, S a 중 하나이고 $1 \le a, b \le 6$이다. 한 격자의 명세 중 12개는 도미노이고 정확히 1개는 싱글턴이며, 도미노 12개는 서로 다르다. 한 격자의 명세가 여러 줄에 걸쳐 나올 수 있으므로 입력을 토큰의 연속으로 읽어야 한다.

명세는 주어진 순서대로 처리한다. 격자를 위에서 아래로, 각 줄에서는 왼쪽에서 오른쪽으로 훑어 처음 만나는 빈 칸에 그 명세를 놓는다. H a b는 그 칸에 a를, 오른쪽 칸에 b를 놓는다. V a b는 그 칸에 a를, 아래 칸에 b를 놓는다. S a는 그 칸에 a를 놓는다. 입력은 항상 격자를 빈틈없이 채운다.

격자마다 한 줄에 Case i: s를 출력한다. $i$는 1부터 시작하는 격자 번호이고, $s$는 도미노를 최대 한 번 바꿔서 얻을 수 있는 가장 높은 점수다.

심심풀이 문제. 점수가 가장 높은 Domiyahtzee 격자는 무엇일까? 출제자가 찾은 격자는 498점이다. 이 물음은 채점과 관계가 없다.