hackercupai/hackercup huggingface dataset:
You're a proud boomerang farmer, like your father before you (and his father
before him, but quite unlike his grandfather). Your boomerang field can be
modelled as a 2D grid of square cells, with **M** rows and **N** columns. Each
cell contains a boomerang lying flat on the ground, in one of four possible
orientations called A, B, C, and D:

![]({{PHOTO_ID:263973168278076}})

For example, your field might look as follows:

![]({{PHOTO_ID:572878846700654}})

As you can see, there are 2 points at which pairs of boomerangs are touching
one another at their endpoints. As all boomerang farmers know, that could
stunt the growth of your precious boomerangs!

Fortunately, you can salvage the situation by rotating boomerangs by integer
multiples of 90 degrees. In particular, rotating a single boomerang by 90
degrees either clockwise (for example, changing its orientation from A to B)
or counter-clockwise (for example, from A to D) takes 1 minute. You may rotate
a single boomerang multiple times.

You have **K** minutes of free time that you can use to fix up your field as
well as you can (though you don't have to use all of this time). What's the
minimum number of pairs of touching boomerangs that you can end up with at the
end of this time? For example, given 2 minutes to work on the above field, you
could rotate the top-right boomerang counter-clockwise and the bottom-left one
clockwise to end up with no touching boomerangs:

![]({{PHOTO_ID:3313736538657036}})

### Input

Input begins with an integer **T**, the number of fields. For each field,
there is first a line containing the space-separated integers **M**, **N**,
and **K**. Then, **M** lines follow, the **i**th of which contains a string of
length **N** representing the **i**th row of the field as described above.

### Output

For the **i**th field, print a line containing "Case #**i**: " followed by the
minimum number of touching boomerang pairs that will remain after you work the
field optimally.

### Constraints

1 ≤ **T** ≤ 100
1 ≤ **M**, **N** ≤ 100
0 ≤ **K** ≤ 1,000

### Explanation of Sample

The fifth field is the example given above.