Code Jam의 해

2008년은 변화와 전환의 해이자 새로운 시대의 시작으로 알려질 것이다. 물론 새로운 Google Code Jam 형식을 말하는 것이다. 이 대회의 도입으로 하나의 해에 수많은 훌륭한 프로그래밍 대회가 한데 몰렸고, 사람들은 이 해를 Code Jam의 해라고 부르기 시작했다. 열정적인 참가자 Sphinny는 그해의 달력을 보다가 아주 많은 프로그래밍 대회가 예정되어 있다는 사실을 발견한다. 그녀는 달력에서 그해의 모든 날짜를 다음 세 가지 방식 중 하나로 표시했다.

• White: She는 이날 대회에 참가하지 않는다. 예정된 대회가 없거나, 그녀에게 더 중요한 일이 있다(분명 인생에는 다른 좋은 일들도 있을 것이다!).

• Blue: She는 이날 대회에 반드시 참가한다.

• 물음표: 예정된 대회가 있지만, 참가할지는 아직 결정하지 않았다.

참고: 문제를 단순화하기 위해 예선이라는 개념은 없다고 가정한다. 다른 대회의 참가 자격을 얻기 위해 어떤 대회에 참가할 필요는 없다.

Sphinny가 사는 세계는 우리의 세계와 다소 다르므로, 그녀의 달력에는 언급해야 할 몇 가지 특징이 있다. 달력에는 N개의 달이 있고, 각 달에는 정확히 M일이 있다.

아래 그림은 달이 5개이고, 각 달에 날짜가 8개이며, 파란색 날짜가 15개, 물음표가 5개인 달력을 나타낸다.

아름다운 달력을 바라보던 Sphinny는 그해의 각 날짜에 이웃이 최대 4개 있다고 정했다. 같은 달의 이전 날짜, 같은 달의 다음 날짜, 이전 달의 같은 날짜, 다음 달의 같은 날짜가 이웃이다.

Sphinny는 이 대회들로부터 얻는 행복을 최대화하려 하며, 모든 파란색 날짜의 값을 합산하여 대회가 자신의 행복에 미치는 영향을 추산한다. 각 파란색 날짜의 값은 다음과 같이 계산한다.

• 초깃값은 4이다.

• 해당 날짜의 파란색 이웃마다 값을 1만큼 감소시킨다.

Sphinny가 대회를 좋아한다고 생각할 수도 있지만, 이틀 연속으로 참가하면 조금 피곤해진다. 또한 미관상의 이유로 두 달 연속 같은 날짜에 참가하는 것도 그다지 좋지 않다.

Sphinny는 이제 한 해의 계획을 세우고, 물음표가 있는 모든 날짜를 흰색으로 할지 파란색으로 할지 결정하려 한다. 그녀의 목표는 단순히 행복 값을 최대화하는 것이다.

다음 그림은 위 예제의 해답을 보여 준다. 물음표 두 개를 파란색 날짜로 바꾸고 나머지 세 개를 흰색 날짜로 바꾸면 행복 값 42을 얻을 수 있다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ M, N ≤ 15.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ M, N ≤ 50.

입력 파일의 첫 번째 줄에는 케이스의 수 T가 주어진다. 이어서 다음 형식의 T개 케이스가 주어진다. 첫 번째 줄은 "N M" 형식이며, N과 M은 각각 달의 수와 한 달의 날짜 수를 나타내는 두 수이다. 다음 N개의 줄에는 각각 길이가 M인 문자열이 주어진다. i번째 문자열의 j번째 문자는 {'#', '.', '?'} 중 하나이며, i번째 달의 j번째 날짜 상태를 나타낸다. '#'은 파란색 날짜, '.'은 흰색 날짜, '?'는 물음표가 있는 날짜를 나타낸다.

각 입력 케이스에 대해 다음 형식으로 한 줄을 출력한다.

Case #X: Y

여기서 X는 1 기준의 케이스 번호이고, Y는 최대 행복 값이다.

두 번째 예제가 위 그림에 나온 예제라는 점에 유의한다.