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:

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

Note: To simplify the problem, we'll assume that there is no concept of qualification: you don't have to participate in one contest to be eligible for another.

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:

• The initial value is 4.
• For each blue neighbour the day has, decrease the value by 1.

You may think that Sphinny likes the contests, but participating on two consecutive days makes her a little tired. And for aesthetic reasons, participating on the same day in two consecutive months is also not so great.

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 j-th character in the i-th string is one of {'#', '.', '?'}, which gives the status of the j-th day in the i-th 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: Y

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

Limits

Memory limit: 1GB.

1 ≤ T ≤ 100.

Small dataset (Test set 1 - Visible; 7 Points)

Time limit: 30 5 seconds.

1 ≤ M, N ≤ 15.

Large dataset (Test set 2 - Hidden; 23 Points)

Time limit: 120 10 seconds.

1 ≤ M, N ≤ 50.

Sample

2
3 3
.?.
.?.
.#.
5 8
.#...##.
.##..?..
.###.#.#
??#..?..
###?#...

Case #1: 8
Case #2: 42

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