Problem
The year 2008 will be known as a year of change and transition, the
start of a new era: we're talking, of course, about the new Google Code
Jam format. The introduction of this contest has jammed so many great
programming competitions together in a single year that people have
started calling it The Year of Code Jam.
Sphinny, a passionate contestant, is looking at her calendar of the year
and discovering that a great number of programming contests has been
scheduled. She has marked every day of the year on the calendar in one
of the three ways:
Being in a world that is somewhat different from ours, Sphinny's calendar has some features we must mention: It has N months, and each month has exactly M days.
The picture below depicts a calendar with 5 months, 8 days in each month, 15 blue days, and 5 question marks.
Looking at her beautiful calendar, Sphinny has decided that each day has up to 4 neighbors in the year: The previous day in the same month, the next day in the same month, the same day in the previous month, and the same day in the next month.
Sphinny wants to maximize her happiness from these contests, and she estimates the effect of the contests on her happiness as a summation of values for all the blue days. For each blue day, the value is computed as follows:
Sphinny wants to plan her year now, and decide for every day with a question mark whether it should be white or blue. Her goal is simply to maximize the happiness value.
The following picture shows a solution for the example above. By changing two question marks to blue days, and the other three to white days, she can achieve a happiness value of 42.
Input
The first line in the input file contains the number of cases T. This is followed by T cases in the following format.
The first line is of the form "N M", where N and M are two numbers giving the number of months and the number of days per month.
The next N lines each contain a string of length M. The jth character in the ith
string is one of {'#', '.', '?'}, which gives the status of the jth
day in the ith month. '#' indicates a blue day, '.' indicates a white
day, and '?' indicates a day with a question mark.
Output
For each input case, you should output a line in the format:
Case #X: Ywhere X is the 1based case number, and Y is the maximum happiness value.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ M, N ≤ 15.
Large dataset
1 ≤ M, N ≤ 50.
Sample
Input 
Output 
2

Case #1: 8

Note that the second sample is our example in the pictures above.
Points  Correct  Attempted 

7pt  47  68 
23pt  6  9 