코드 잼의 해 (Large)

2008년은 변화와 전환의 해, 새로운 시대가 시작된 해로 기억된다. 바로 새로운 코드 잼 형식이 나온 해다. 이 대회가 생기면서 한 해에 좋은 프로그래밍 대회가 워낙 많이 몰렸고, 사람들은 그 해를 코드 잼의 해라고 부르기 시작했다.

대회를 좋아하는 참가자 스핀니는 올해 달력을 보다가 프로그래밍 대회 일정이 이미 아주 많이 잡혀 있다는 사실을 알았다. 스핀니는 달력의 모든 날을 다음 세 가지 중 하나로 표시했다.

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

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

스핀니가 사는 세계는 우리 세계와 조금 달라서 달력도 다르다. 한 해는 $N$개월이고, 각 달은 정확히 $M$일이다.

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

한 해에서 각 날의 이웃은 최대 4개다. 같은 달의 이전 날, 같은 달의 다음 날, 이전 달의 같은 날, 다음 달의 같은 날이 이웃이다.

스핀니는 대회가 행복도에 주는 영향을 파란색 날마다 계산한 값의 합으로 본다. 파란색 날 하나의 값은 다음과 같이 정한다.

• 처음 값은 4이다.
• 그 날의 파란색 이웃 하나마다 값이 1 줄어든다.

스핀니는 대회를 좋아하지만 이틀 연속 참가하면 조금 피곤하다. 연속한 두 달의 같은 날에 참가하는 것도 달력 모양이 예쁘지 않다.

스핀니는 이제 한 해를 계획한다. 물음표로 표시한 날을 흰색으로 둘지 파란색으로 바꿀지 정해서 행복도의 합을 최대로 만드는 것이 목표다.

다음 그림은 위 달력의 한 가지 답이다. 물음표 두 개를 파란색 날로 바꾸고 나머지 세 개를 흰색으로 두면 행복도 42가 된다.

첫째 줄에 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 케이스가 다음 형식으로 주어진다.

각 케이스의 첫째 줄에는 "$N$ $M$"이 주어진다. $N$은 달의 수, $M$은 한 달의 날짜 수다.

다음 $N$개의 줄에는 길이가 $M$인 문자열이 하나씩 주어진다. $i$번째 문자열의 $j$번째 문자는 '#', '.', '?' 중 하나이고, $i$번째 달의 $j$번째 날 상태를 나타낸다. '#'은 파란색 날, '.'은 흰색 날, '?'는 물음표로 표시한 날이다.

제한

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

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

Case #X: Y

$X$는 1부터 시작하는 케이스 번호이고, $Y$는 행복도의 최댓값이다.

샘플 입력의 두 번째 달력이 위 그림에 그려진 달력이다.