The Year of Code Jam (Large)

The year 2008 is remembered as a year of change and transition, the start of a new era: the new Code Jam format. So many good programming contests were packed into that single year that people started calling it The Year of Code Jam.

Sphinny loves contests. Looking at her calendar for the year, she finds that a large number of programming contests are already scheduled. She has marked every day of the year on the calendar in one of three ways.

• White: she will not take part in a contest on this day. Either no contest is scheduled, or she has more important things to do (there are other good things in life).
• Blue: she will definitely take part in a contest on this day.
• Question mark: a contest is scheduled, but she has not decided yet whether she will take part.

To keep the problem simple, assume there is no qualification. Taking part in one contest is never required in order to enter another one.

Sphinny lives in a world that is a little different from ours, so her calendar is different too. The year has $N$ months, and every month has exactly $M$ days.

The picture below shows a calendar with 5 months, 8 days per month, 15 blue days, and 5 question marks.

Every day in the year has at most 4 neighbors: 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 measures the effect of the contests on her happiness as the sum of one value per blue day. The value of a single blue day is computed like this.

• The initial value is 4.
• For every blue neighbor the day has, the value drops by 1.

Sphinny likes contests, but taking part on two days in a row makes her a little tired. Taking part on the same day in two consecutive months does not look good on the calendar either.

Sphinny now plans her year. For every day marked with a question mark she decides whether it stays white or becomes blue, and her goal is to maximize the total happiness value.

The next picture shows one answer for the calendar above. Turning two question marks into blue days and leaving the other three white gives a happiness value of 42.

The first line contains the number of cases $T$. Then $T$ cases follow, each in the format below.

The first line of a case is "$N$ $M$", where $N$ is the number of months and $M$ is the number of days per month.

Each of the next $N$ lines contains one string of length $M$. The $j$-th character of the $i$-th string is one of '#', '.', '?' and gives the status of the $j$-th day of the $i$-th month. '#' is a blue day, '.' is a white day, and '?' is a day marked with a question mark.

Limits

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

For each case, print one line in the format

Case #X: Y

where $X$ is the 1-based case number and $Y$ is the maximum happiness value.

The second calendar in the sample input is the calendar drawn in the pictures above.