뛰어라 도마뱀

용재는 애완 도마뱀들과 함께 던전을 돌다가 이상한 방에 입장했다. 건질 게 없나 주위를 둘러보던 용재는 뒤를 돌아보고 깜짝 놀랐다. 막내 도마뱀이 함정을 밟아 방의 바닥이 사라져버린 것이다! 밑에서는 불길이 올라오기 시작했고, 도마뱀들은 바닥이 사라지고 남은 기둥 위에 서 있다.

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

방을 \(N \times M\) 격자로 볼 때 한 칸에 최대 하나의 기둥이 존재한다. 도마뱀은 자신이 현재 위치한 기둥에서 맨해튼거리(\(|{n_i} - {n_j}| + |{m_i} - {m_j}|\))가 \(D\) 이내인 다른 기둥으로 도약할 수 있다. 도약한 도마뱀이 방 밖으로 빠져나오면 방을 탈출한 것으로 본다.

하지만 남아 있는 기둥들은 위태로워서, 버틸 수 있는 도약 횟수가 정해져 있다. 한 도마뱀이 어떤 기둥에서 도약하여 다른 기둥으로 갈 때, 기존 기둥은 점점 약해지고, 한계를 넘으면 무너져 내린다. 같은 시간 동안 하나의 기둥에는 최대 하나의 도마뱀만 서 있을 수 있다.

첫 줄에는 테스트케이스의 개수 \(T(T \lt 25)\)가 입력된다. 각 테스트케이스의 첫 줄에는 방의 세로 크기 \(N\)과 도마뱀의 최대 도약거리 \(D(1 \le D \le 4)\)가 주어진다. 이어서 방의 정보가 각각 \(N\)개의 줄에 걸쳐서 두 번 주어진다. 처음 상태는 각각의 기둥이 버틸 수 있는 도약 횟수를 나타낸다. 한 기둥이 견딜 수 있는 도약 횟수는 최대 3번이며, 주어진 숫자가 0인 칸은 기둥이 존재하지 않는다. 두 번째는 도마뱀의 위치를 나타낸다. 도마뱀이 존재하는 칸은 'L'로, 이외의 칸은 '.'으로 표시되며, 기둥이 없는 곳에 도마뱀이 존재하는 경우는 없다.

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

각각의 테스트 케이스마다 아래의 예제 출력의 형식에 따라 탈출하지 못하는 도마뱀의 수를 한 줄에 출력하라.

주의 : 모든 길을 조사하는 Brute Force 방법의 경우, 주어진 시간을 초과할 수 있다.