Irrigation Lines

A plantation is made of rectangular fields, and each field is divided into square zones. Crops are rotated, so in one season some zones are planted and the others lie fallow.

Every field has its own irrigation system. The main water line runs around the field, and valves connect it to the lateral irrigation lines. There is one line for each row of zones and one line for each column, so a field with $M$ rows and $N$ columns has $M + N$ lines. Water flows through a line while its valve is open and stops when the valve is closed. A planted zone is watered as long as the line of its row or the line of its column is open. On an open line, the emitters over the zones that need no water are closed.

To keep the management effort low, the system has to open as few lines as possible. Read the layout of a field and compute the smallest number of irrigation lines that must be open to water every planted zone.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each test case starts with a line holding the number of rows $M$ and the number of columns $N$ ($1 \le M, N \le 100$), separated by a space. The next $M$ lines each contain a string of $N$ characters, where 1 marks a planted zone and 0 marks a fallow zone.

For each test case, print one line in the form "Case #X: Y", where $X$ is the test case number starting from 1 and $Y$ is the smallest number of irrigation lines that must be open. Put one space after the colon.