시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 9 7 53.846%

문제

ACM-ICPC 리저널 대회가 열리기 전, 현장 담당관과 자원봉사자들은 매우 바쁘다.

그들의 임무 중 하나는 대회장의 테이블을 적절히 배치하여 인접한 두 테이블에는 서로 다른 학교 출신의 팀이 앉도록 하는 것이다.

이 일은 상당히 힘든 일이기 때문에 일반적으로 사람이 직접 하기보다는 프로그램을 통해 수행한다. 올해는 심사위원들이 이 일을 맡게 되었다.

심사위원들은 프로그램을 통해 자리 배치를 끝냈다. 그 후 가만히 생각해보니, 이 자리 배치 문제가 대회 문제로 상당히 좋을 것 같았다. 따라서 심사위원들은 이 문제의 일부를 실제 대회 문제로 출제하기로 하였다.

심사위원들의 프로그램 작동 방식은 아주 단순하다. 우선 그냥 임의로 자리를 배치시킨다. 이후 어떤 인접한 두 자리에 같은 대학 출신의 두 팀이 앉게 되는지 확인한다. 만일 그러한 자리가 존재한다면 그러한 배치로 혜택을 받는 학교, 즉 인접한 자리에 같은 학교 출신 팀이 앉게 되는 학교가 총 몇 개인지 센다.

대회장은 2차원 평면에 N개의 행, M개의 열로 이루어진 표로 나타낼 수 있다.

표의 각 칸에는 한 팀이 앉거나 아무 팀도 앉지 않는다.

각 팀은 최대 8개의 인접한 팀을 가질 수 있다. 만일 자리가 모서리 쪽이라거나, 주변에 빈 자리가 있는 경우엔 8개 미만의 인접한 팀을 갖게 된다.

예를 들어 위와 같은 상황에서, 팀 E는 7개의 인접한 팀 A, B, C, D, F, G, H를 갖는다.

또한 팀 A는 3개의 인접한 팀 B, D, E를 갖는다.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )

각 테스트 케이스의 첫 줄엔 대회장의 세로 길이와 가로 길이 N, M이 주어진다. ( 1 ≤ N, M ≤ 100 )

이어 N줄에 걸쳐 M개의 정수로 각 자리에 어떤 팀이 앉게 되는지가 주어진다. 팀의 ID는 1부터 100까지의 정수로 표현되며, 만일 ID가 -1로 주어진다면 그 자리가 비어있음을 의미한다.

출력

각 테스트 케이스마다, 인접한 같은 학교 출신의 팀을 가지는 학교가 총 몇 개인지 출력한다.

예제 입력

3
3 3
1 2 3
2 2 2
1 1 1
3 3
1 2 3
3 -1 1
2 -1 2
3 3
1 2 3
-1 1 5
1 2 4

예제 출력

2
0
1

힌트