뛰어라 도마뱀

용재는 애완 도마뱀들과 함께 던전을 탐험하다가 이상한 방에 들어섰다. 쓸 만한 물건이 없나 둘러보던 용재가 뒤를 돌아본 순간, 막내 도마뱀이 함정을 밟아 방의 바닥이 통째로 사라져 버렸다. 아래에서는 불길이 치솟기 시작했고, 도마뱀들은 바닥이 사라진 뒤 남은 기둥 위에 아슬아슬하게 서 있다.

도마뱀들은 준서에게 빌린 것이라, 용재는 잃어버린 도마뱀의 수를 준서에게 보고해야 한다. 잃어버린 도마뱀이 많을수록 준서가 더 크게 화를 낼 것이므로, 용재는 최대한 많은 도마뱀을 탈출시켜 보고할 수를 최소로 만들고 싶다.

방을 $N \times M$ 격자로 나타내면 한 칸에는 최대 한 개의 기둥이 있다. 도마뱀은 지금 서 있는 기둥에서 맨해튼 거리 $|n_i - n_j| + |m_i - m_j|$ 가 $D$ 이하인 다른 기둥으로 도약할 수 있다. 도약한 도마뱀이 방 바깥으로 나가면 탈출한 것으로 본다.

남은 기둥들은 위태로워서 버틸 수 있는 도약 횟수가 정해져 있다. 도마뱀이 어떤 기둥에서 다른 곳으로 도약하면 그 출발 기둥은 조금씩 약해지고, 버틸 수 있는 횟수를 넘기면 무너진다. 또한 같은 시각에 하나의 기둥 위에는 최대 한 마리의 도마뱀만 서 있을 수 있다.

첫 줄에 테스트 케이스의 수 $T$ ($T < 25$) 가 주어진다.

각 테스트 케이스의 첫 줄에는 방의 세로 크기 $N$ 과 도마뱀의 최대 도약 거리 $D$ ($1 \le D \le 4$) 가 주어진다. 이어서 방의 정보가 각각 $N$ 개의 줄로 두 번 주어진다.

첫 번째 격자는 각 기둥이 버틸 수 있는 도약 횟수를 나타낸다. 한 기둥이 버틸 수 있는 도약 횟수는 최대 3번이며, 숫자가 $0$ 인 칸에는 기둥이 없다.

두 번째 격자는 도마뱀의 위치를 나타낸다. 도마뱀이 있는 칸은 L, 그 밖의 칸은 . 으로 표시하며, 기둥이 없는 칸에 도마뱀이 있는 경우는 없다.

모든 방의 크기는 $N \times M$ 직사각형이고, $1 \le N, M \le 20$ 이다.

각 테스트 케이스마다 탈출하지 못한 도마뱀의 수를 다음 형식에 맞추어 한 줄씩 출력한다. 여기서 $x$ 는 1부터 시작하는 테스트 케이스 번호이다.

• 탈출하지 못한 도마뱀이 없으면: Case #x: no lizard was left behind.
• 정확히 한 마리이면: Case #x: 1 lizard was left behind.
• 두 마리 이상 $k$ 마리이면: Case #x: k lizards were left behind.

주의: 모든 경로를 탐색하는 완전 탐색(브루트 포스) 방법은 주어진 시간을 초과할 수 있다.