전구 모두 켜기

직사각형 패널은 $R$개의 행으로 이루어져 있고, 각 행에는 전구가 $C$개씩 달려 있다. 행 번호는 0부터 $R-1$까지, 열 번호는 0부터 $C-1$까지다. 전구 가운데 일부는 켜져 있고 나머지는 꺼져 있다.

패널에는 스위치판이 연결되어 있다. 스위치는 $R$행 $C$열의 직사각형으로 놓여 있어서 패널과 크기가 같다.

스위치 하나를 누르면 전구 일부의 상태가 뒤집힌다. 켜져 있던 전구는 꺼지고, 꺼져 있던 전구는 켜진다. 좀 더 정확히 말하면 좌표가 $(\text{row}, \text{col})$인 스위치를 누를 때 $x \le \text{row}$이고 $y \le \text{col}$인 모든 좌표 $(x, y)$의 전구가 상태를 바꾼다. 즉 $(0, 0)$과 $(\text{row}, \text{col})$을 마주 보는 두 꼭짓점으로 삼는 직사각형 안의 전구가 모두 뒤집힌다.

전구의 초기 상태를 담은 행렬이 주어진다. 문자 1은 켜진 전구, 문자 0은 꺼진 전구를 뜻한다.

모든 전구를 한꺼번에 켜 놓으려면 스위치를 최소 몇 번 눌러야 하는지 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $R$과 $C$가 주어진다. 이어지는 $R$개의 줄에는 각각 문자가 $C$개 주어지고, 이 $R \times C$ 행렬이 전구의 초기 상태다. $R$과 $C$는 1 이상 500 이하다.

각 테스트 케이스마다 Case #x: M 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고 1부터 시작한다. $M$은 모든 전구를 한꺼번에 켜기 위해 필요한 최소 누름 횟수다.