스키 리프트

기후 변화로 알래스카의 완만한 산악 지대가 사계절 스키를 즐기기에 완벽한 장소가 되었다. 하지만 이 지역을 성공적인 스키장으로 만들려면 스키 리프트가 필요하다. 스키를 타는 사람은 위로 걸어 올라가는 것을 좋아하지 않는다. 그들은 내리막으로 활강하기를 원하며, 필요할 때는 잠시 같은 높이로 이동하는 정도는 감수할 수 있다.

이 지역을 최적으로 활용하려면, 임의의 한 지점에서 출발한 스키어가 오직 내리막으로 활강하거나 같은 높이로 이동하고 때때로 스키 리프트를 이용하는 것만으로 다른 임의의 지점에 도달할 수 있어야 한다.

이 조건을 만족하도록 충분한 수의 스키 리프트를 계획하고 건설해야 한다. 반대로 필요 이상으로 리프트를 많이 짓는 것은 돈 낭비이다.

필요한 스키 리프트의 최소 개수는 몇 개인가?

스키 리프트는 높은 기둥 위에 세워지므로, 사이의 지형과 무관하게 어느 지점에서 어느 지점으로든 세울 수 있다고 가정한다. 스키 리프트는 한 방향으로만 운행한다(단방향).

알래스카에서는 북, 남, 동, 서 네 방향 외의 방향으로는 스키를 탈 수 없다. 즉 스키어는 상하좌우로 인접한 칸으로만 이동할 수 있고, 그 칸의 높이가 현재 칸의 높이보다 낮거나 같을 때에만 활강으로 이동할 수 있다.

입력의 첫 줄에는 테스트 케이스의 개수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 두 정수 $w$와 $l$이 주어진다 ($1 \le w, l \le 500$). 각각 지역의 너비와 길이이다.
• 이어서 $w$개의 줄이 주어지고, 각 줄에는 $l$개의 정수 $h_{ij}$가 있다 ($0 \le h_{ij} \le 10^9$). 이는 지역의 각 지점의 높이를 나타낸다.

각 테스트 케이스마다 건설해야 하는 스키 리프트의 최소 개수를 한 줄에 정수 하나로 출력한다.