题目描述 一个 n*n的方格图，其中 .代表空地，h 代表障碍。 Noder希望从图的左上走到右下，每次只能向下或向右走，如果碰到障碍，则必须绕过。 由于 Noder本身不擅长转向，规定在整个过程中，转向次数不能超过m 次（m<=3 ），问在这些限制下，从 左上走到右下，有多少种不同的走法。

输入

本题包含多组测试数据。 第一行输入一个数T，表示测试组数。 之后对于每组测试，第一行包含 n 和 m。其中n是方格图的大小，m是转向次数。 后面是一个n*n的方格图，其中.代表空地，可以随意穿行，H代表障碍。 其中1≤T≤50，2≤n≤50，0≤m≤3。 输出 输出 T 行，对应 T 个测试的答案

样例输入 Copy

4

3 1

...

...

...

3 2

...

...

...

3 3

.H.

H..

...

4 3

...H

.H..

....

H...

样例输出 Copy

2

4

0

6

提示 对于10%的数据，1 ≤ T ≤ 10,2 ≤ n ≤ 5 ； 另有10%的数据，m = 1 ； 另有30%的数据， m = 2； 对于100%的数据 。1 ≤ T ≤ 50,2 ≤ n ≤ 50,0 ≤ m ≤ 3