격자 0 만들기

음수가 아닌 정수로 채워진 격자가 주어진다. 이 격자에 다음 연산을 원하는 횟수만큼 행할 수 있다.

1. 격자에서 가로 또는 세로로 인접한 칸 2개를 고른다.
2. 고른 칸 각각에 대해, 그 값이 양수이면 1 감소시킨다.

값이 이미 0인 칸을 골라도 되며, 그 칸은 0으로 남는다.

다음 그림은 2×2 격자에 연산을 네 번 이어서 행해 모든 수를 0으로 만든 과정이다. 노란색으로 칠한 두 칸이 그 단계에서 고른 칸이다.

이 예에서는 네 번의 연산으로 모든 수를 0으로 만들었고, 이보다 적은 횟수로는 만들 수 없다.

격자가 주어졌을 때 모든 수를 0으로 만드는 데 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

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

각 테스트 케이스의 첫째 줄에는 격자의 행 개수 $n$과 열 개수 $m$이 주어진다 ($2 \le n, m \le 50$). 이어지는 $n$개의 줄에는 격자의 해당 행에 있는 정수 $m$개가 열 순서대로 주어진다. 각 정수는 $0$ 이상 $1{,}000$ 이하이다.

각 테스트 케이스마다 필요한 연산의 최소 횟수를 한 줄에 출력한다.