Description

一队流浪蜥蜴进入了迷宫中的一个陌生房间，当四处寻找隐藏的宝藏时，一只新手踩在一块看起来平淡无奇的石头上，房间的地板突然消失了！每一只蜥蜴都站在一根看起来脆弱的柱子上，下面开始燃烧。

别留下蜥蜴！请让尽可能多的蜥蜴离开房间，报告伤亡数。

柱子排列成一个网格，每根柱子都距离其东、西、北和南的柱子各$1$个单元。

网格边缘的柱子距离房间边缘$1$个单位$（$安全$）$。

并非所有柱子上都有蜥蜴。

蜥蜴可以跳跃到当前柱子$d$个单位内任何未被占据的柱子上。

若一只蜥蜴站在一根柱子上，离房间边缘的跳跃距离很近，那么它总是可以跳到安全的地方。

但有一个陷阱：每次跳跃后，每根柱子都会变弱，很快就会坍塌，其他蜥蜴就不能再使用了。

跳到柱子上不会使柱子变弱或倒塌，只是跳下去会使柱子变弱并最终倒塌。

在任何时候，在一根柱子上只可以有一只蜥蜴。

Format

Input

第$1$行为一个整数$T$$（$$T$$≤$$2$$5$$）$，表示测试用例的数量。

每个测试用例都以正整数$n$开始，表示地图中的行数，然后是一个非负整数$d$$（$$1$$≤$$d$$≤$$3$$）$，表示蜥蜴的最大跳跃距离。

接下来是两个地图，每个地图都是一行一行的字符。

第$1$个地图将在每个位置都包含一个数字$（$$0$～$3$$）$，表示该位置的柱子在塌陷前将保持的跳跃次数$（$$0$表示没有柱子$）$；

在第$2$张地图上，每个蜥蜴在柱子上的位置都有一个“$L$”，每个空柱子都有一个“.”。

在没有柱子的地方永远不会有蜥蜴。

每个地图都为$n$×$m$的矩形$（$$1$$≤$$n$，$m$$≤$$2$$0$$）$。

Output

对每个测试用例，都按样例格式单行输出无法逃脱的蜥蜴数量。

Samples

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..
........
........

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.

来源

HDU2732