本题没有可用的提交语言。

描述

你率领的蜥蜴小队在探索迷宫时进入了一个奇怪房间。当你们正在搜寻隐藏的宝藏时，一名新兵踩到了一块看似无辜的石头，房间地板突然消失！每只蜥蜴都站在摇摇欲坠的石柱上，下方燃起了熊熊烈火...

不要放弃任何一只蜥蜴！尽可能让更多蜥蜴逃出房间，并报告伤亡数量。

房间内的石柱呈网格状排列，每个石柱与东、西、南、北相邻石柱相距$1$单位距离。位于网格边缘的石柱距离房间边缘（安全区域）$1$单位距离。并非所有石柱上都有蜥蜴。每只蜥蜴可以跳跃到当前所在石柱$d$单位距离内任何未被占据的石柱上。站在距离房间边缘跳跃范围内的蜥蜴总能跳向安全区域...但有个限制：每个石柱在每次被跳离后会变得脆弱，最终坍塌无法再被其他蜥蜴使用。跳到石柱上不会使其变脆弱或坍塌；只有从石柱跳离才会导致其逐渐损坏。任何时候一个石柱上只能站一只蜥蜴。

输入

输入文件首行包含一个整数表示测试用例数量（最多$25$个）。每个测试用例包含：
• 一个正整数$n$表示地图行数
• 一个非负整数$d$表示蜥蜴最大跳跃距离
随后是两个$n \times m$的字符矩阵：

1. 第一个矩阵每个位置包含数字$0$-$3$，表示该位置石柱在坍塌前能承受的跳跃次数（$0$表示无石柱）
2. 第二个矩阵用'L'表示有蜥蜴的位置，'.'表示空石柱
   保证蜥蜴不会出现在没有石柱的位置

数据规模：$1 \leq n \leq 20$，$1 \leq m \leq 20$，跳跃距离$1 \leq d \leq 3$。

输出

对每个测试用例，输出一行表示未能逃生的蜥蜴数量，格式如下方示例所示。

输入数据 1

4
3 1
1111
1111
1111
LLLL
LLLL
LLLL
3 2
00000
01110
00000
.....
.LLL.
.....
3 1
00000
01110
00000
.....
.LLL.
.....
5 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........

输出数据 1

Case #1: 2 lizards were left behind.
Case #2: no lizard was left behind.
Case #3: 3 lizards were left behind.
Case #4: 1 lizard was left behind.

提示
暴力枚举所有路径的方法可能会超出时间限制。

来源

2005年美国中北部地区竞赛