전구

각 발사가 같은 열의 아래쪽과 같은 행의 왼쪽 전구까지 토글할 때, 모든 전구를 켜는 최소 발사 횟수를 구한다.

보통5그리디구현면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제1

문제

그렉에게는 $m \times n$ 격자 모양으로 놓인 전구가 있고, 그렉은 이 전구를 모두 켜려고 한다. 처음에는 켜진 전구도 있고 꺼진 전구도 있다. 그렉은 전구에 레이저를 쏘아 상태를 바꿀 수 있다. 어떤 전구에 레이저를 쏘면 그 전구가 켜져 있으면 꺼지고 꺼져 있으면 켜진다. 이때 같은 열에서 그 전구보다 아래에 있는 모든 전구와 같은 행에서 그 전구보다 왼쪽에 있는 모든 전구도 함께 상태가 바뀐다.

모든 전구를 켜려면 레이저를 최소 몇 번 쏘아야 하는지 구하시오.

입력

첫째 줄에 테스트 케이스의 수 $T$ ( $1 \le T \le 10$ )가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $m$ 과 $n$ ( $1 \le m, n \le 400$ )이 공백으로 구분되어 주어진다. 다음 $m$ 개의 줄에는 각각 1과 0으로 이루어진 길이 $n$ 의 문자열이 주어진다. 1은 켜진 전구, 0은 꺼진 전구를 나타낸다.

출력

각 테스트 케이스마다 모든 전구를 켜기 위해 레이저를 쏘아야 하는 최소 횟수를 한 줄에 출력한다.

힌트

첫 번째 테스트 케이스에서는 오른쪽 맨 위 전구에 레이저를 한 번 쏘면 꺼져 있던 전구가 모두 켜지고 켜져 있던 전구는 하나도 바뀌지 않는다.

두 번째 테스트 케이스에서는 왼쪽 맨 위 전구와 오른쪽 맨 위 전구에 레이저를 쏘면 된다.