코드 잼의 해 (스몰)

2008년은 변화와 전환의 해, 새로운 시대의 시작으로 기억될 것이다. 물론 여기서 말하는 것은 새로운 Google Code Jam 형식이다. 이 대회가 생기면서 한 해에 훌륭한 프로그래밍 대회가 몰렸고, 사람들은 그 해를 코드 잼의 해라고 부르기 시작했다.

열성적인 참가자 Sphinny가 한 해의 달력을 보니 프로그래밍 대회 일정이 아주 많이 잡혀 있다. Sphinny는 달력의 모든 날을 다음 세 가지 중 하나로 표시했다.

• 흰색: 이 날에는 대회에 참가하지 않는다. 대회 일정이 없거나, 더 중요한 일이 있다.
• 파란색: 이 날에는 반드시 대회에 참가한다.
• 물음표: 대회 일정은 있지만 참가할지 아직 정하지 않았다.

문제를 단순하게 만들기 위해 예선 통과라는 개념은 없다고 가정한다. 어떤 대회에 참가하려고 다른 대회에 먼저 참가해야 하는 일은 없다.

Sphinny가 사는 세계는 우리 세계와 조금 다르고, 달력에도 짚어 둘 특징이 있다. 한 해는 N개의 달로 이루어지고, 각 달은 정확히 M일이다.

아래 그림은 달이 5개, 한 달이 8일, 파란색 날이 15일, 물음표가 5일인 달력이다.

Sphinny는 한 해 안에서 어떤 날의 이웃을 최대 4개로 정했다. 같은 달의 전날, 같은 달의 다음 날, 이전 달의 같은 날, 다음 달의 같은 날이다.

Sphinny의 행복도는 파란색 날마다 계산한 값을 모두 더한 값이다. 파란색 날 하나의 값은 다음과 같이 정한다.

• 처음 값은 4다.
• 이웃 중 파란색인 날이 하나 있을 때마다 값을 1 줄인다.

Sphinny가 대회를 좋아한다고 해도, 이틀 연속으로 참가하면 조금 피곤하다. 그리고 연속한 두 달의 같은 날에 참가하는 것도 보기에 좋지 않다.

Sphinny는 이제 한 해를 계획하려고 한다. 물음표로 표시한 날을 각각 흰색이나 파란색으로 정해서 행복도를 최대로 만들어라.

아래 그림은 위 예시의 답 하나다. 물음표 5일 중 2일을 파란색으로, 나머지 3일을 흰색으로 정하면 행복도가 42가 된다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

첫 줄에 달의 수 N과 한 달의 일수 M이 공백으로 구분되어 주어진다. 다음 N개의 줄에는 각각 길이 M의 문자열이 주어진다. i번째 문자열의 j번째 문자는 #, ., ? 중 하나로, i번째 달의 j번째 날의 상태를 나타낸다. #는 파란색 날, .는 흰색 날, ?는 물음표로 표시한 날이다.

제한

• $1 \le T \le 100$
• $1 \le M, N \le 15$

각 테스트 케이스마다 한 줄에 다음 형식으로 출력한다.

Case #X: Y

X는 1부터 시작하는 테스트 케이스 번호이고, Y는 최대 행복도다.

예제의 두 번째 테스트 케이스가 위 그림에 나온 달력이다.