Background

下雪了，又到了白色相簿的季节。
北原春希、小木曾雪菜和冬马和纱是年少时很好的朋友。圣诞夜，和纱离开日本前往奥地利，春希和雪菜打算带着圣诞礼物去机场送她。因为他们是很好的朋友，所以春希和雪菜准备了很多礼物。因为正在下大雪，春希的摩托车不能使用了，雪菜只好选出最好的礼物送给和纱。剩下的礼物怎么办呀，这可愁苦了春希。还好这时圣诞老人派出了一些圣诞小精灵来帮他们回收圣诞礼物。圣诞小精灵是魔法生物，会消耗停留的地方的魔力。当一个地方的魔力枯竭时，圣诞小精灵将不能停留在那里。只要将礼物搬到地图之外就可以认为礼物回收成功。春希和雪菜想知道，圣诞小精灵可以帮他们回收多少圣诞礼物。但是春希有很强的自尊心，他不想直接知道答案，所以你需要告诉他有多少圣诞礼物不能被回收。

Description

逃逸问题。圣诞礼物存在于一个$n{\times}m$的矩形网格图上。每个格点有相应的魔力$k$，其中放有圣诞礼物的格点至少有一点魔力。圣诞小精灵的移动方式为跳跃，并且每次移动都会消耗目标格点的一点魔力。神秘的圣诞小精灵在跳跃时沿垂直方向或水平方向，或者先沿垂直方向后沿水平方向（不要问为什么，这是设定）。魔力枯竭的格点的魔力数为0。因为圣诞礼物的数量$N$是确定的，所以聪明的北原春希可以从不能被回收的圣诞礼物的数量$(N-K)$中，推断出能被回收的圣诞礼物的数量$K$。
（OJ出那么坑不会被打死吗？）

Format

Input

一个整数$T(T{\le}25)$代表测试样例的数量。
每一个测试样例的第一行有两个正整数$n,d$，$n$代表网格图的行数，$d$代表圣诞小精灵的最大移动距离。接着是两幅网格图。第一幅图只包含数字$k(0<=k<=6)$，表示对应格点的魔力数。第二幅图只包含字符$'\ L\ '$和字符$'\ .\ '$，$'\ L\ '$表示有圣诞礼物的格点，$'\ .\ '$表示没有圣诞礼物的格点。
输入保证每一个网格图都是一个$n{\times}m$的矩形，其中$1<=n, m<=20$，$n$显式给出，$m$隐式给出。圣诞小精灵的最大移动距离$d$是一个整数，其中$1<=d<=3$。

Output

每一个测试样例，输出一行，说明有多少个圣诞礼物不能被回收。

Sample

Input

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

Output

Case #1: 2 gifts were left behind.
Case #2: no gift was left behind.
Case #3: 3 gifts were left behind.
Case #4: 1 gift was left behind.

Limitation

1s, 4096KiB for each test case.

Source

POJ 2711
Vijos Original