Oil Skimming

A company runs a profitable offshore oil-skimming operation. Large slicks of crude oil float on the sea, waiting to be scooped up. A special plane skims the water's surface to collect the oil. Each scoop covers a 10 m by 20 m rectangle, placed either east-west or north-south. Because every cell is a 10 m square, one scoop covers exactly two orthogonally adjacent cells of the grid (a horizontal or vertical pair). Both of those cells must be oil; if either one is pure ocean water, the collected oil is contaminated and worthless.

Given a map of an oil slick, compute the maximum number of scoops that can be extracted. The map is an $N \times N$ grid in which each cell is a 10 m square of water, marked as either an oil cell or a pure-water cell. The scooped rectangles may not overlap.

The first line contains an integer $K$ ($1 \le K \le 100$), the number of test cases. Each test case begins with a line containing an integer $N$ ($1 \le N \le 600$), the size of the square grid. The next $N$ lines each contain $N$ characters describing one row of the grid: # denotes an oil cell and . denotes a pure-water cell.

For each test case, print a single line in exactly the format Case X: M, where $X$ is the test-case number (starting from 1) and $M$ is the maximum number of oil scoops that can be extracted.