1022: SYH’s Easy Construction Problem

There is a city that needs building constructions. Assume the city consists of n×m grids which means n rows multiply m columns. You can make a building on a grid. However, there are some buildings which has been already built in the city. SYH as the mayor, wants you to build any amount of buildings so as to make the quantity of groups in the city as big as possible.

Here is the definition of group:

1. Group is a set of buildings.

2. For each building in the group, there must exist another building in the group which connects it.

3. For any two buildings in different groups, they mustn’t be connected.

4. Two buildings is connected with each other if and only if they are connecting left and right or up and down. In the other words, their XY-coordinates (x₁, y₁) and (x₂, y₂) should obey “x₁=x₂ and |y₁-y₂|=1” or “y₁=y₂ and |x₁-x₂|=1”.

    Now, give the city initial building status, could you please calculate the biggest possible quantity of groups?

The first line conatins an integer T, means the number of test cases. For each test case, the first line contains two integers n and m. The next n lines contain a 01-string with a length of m describing the city buildings. 0 means no building, and you can make a building here, while 1 means there is already a building here, and you cannot make a building.

For each test case ouput “Case: #x:y” in a single line. x is the test case number (starting from 1), and y is your answer.

4

1 5
00000

1 5
01000

2 4
0010
0000

3 3
111
101
111

Case #1: 3
Case #2: 2
Case #3: 4
Case #4: 1