Lights

A rectangular panel has $R$ rows with $C$ bulbs in each row. The rows are numbered from 0 to $R-1$ and the columns from 0 to $C-1$. Some of the bulbs are on and the rest are off.

The panel is wired to a switch board. The switches sit in a rectangle of $R$ rows and $C$ columns, the same size as the panel.

Pressing one switch flips the state of some bulbs. Bulbs that were on turn off, and bulbs that were off turn on. More precisely, pressing the switch at $(\text{row}, \text{col})$ changes the state of every bulb at $(x, y)$ with $x \le \text{row}$ and $y \le \text{col}$. In other words, it flips every bulb inside the rectangle whose opposite corners are $(0, 0)$ and $(\text{row}, \text{col})$.

You are given a matrix with the initial state of the bulbs. The character 1 is a bulb that is on, and the character 0 is a bulb that is off.

Find the minimum number of presses needed to have every bulb on at the same time.

The first line contains $T$, the number of test cases.

Each test case starts with a line holding two integers $R$ and $C$. The next $R$ lines hold $C$ characters each, and this $R \times C$ matrix is the initial state of the bulbs. $R$ and $C$ are between 1 and 500 inclusive.

For each test case, print one line in the format Case #x: M. Here $x$ is the case number starting from 1, and $M$ is the minimum number of presses needed to have every bulb on at the same time.