该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】
奶牛Bessie正准备从她最喜爱的草地回到她的牛棚。
农场位于一个N × N的方阵上（2 ≤ N ≤ 50），其中她的草地在左上角，牛棚在右下角。Bessie 想要尽快回家，所以她只会向下或向右走。有些地方有草堆（haybale），Bessie 无法穿过；她必须绕过它们。
Bessie 今天感到有些疲倦，所以她希望改变她的行走方向至多 K 次（1 ≤ K ≤ 3）。
Bessie 有多少条不同的从她最爱的草地回到牛棚的路线？如果一条路线中 Bessie 经过了某个方格而另一条路线中没有，则认为这两条路线不同。
【输入格式】
每个测试用例的输入包含T个子测试用例，每个子测试用例描述了一个不同的农场，并且必须全部回答正确才能通过整个测试用例。输入的第一行包含T（1 ≤ T ≤ 50）。每一个子测试用例如下。
每个子测试用例的第一行包含N和K。

以下N行每行包含一个长为N的字符串。每个字符为‘.’，表示这一格是空的；如果为‘H’，表示这一格中有草堆。输入保证农场的左上角和右下角没有草堆。
【输出格式】
输出T行，第i行包含在第i个子测试用例中Bessie可以选择的不同的路线数量。

【样例输入输出1】
样例输入（walk.in）

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

样例输出（walk.out）
2
4
6
2
0
0
6
【数据规模与约定】
测试点2满足K = 1。
测试点3-5满足K = 2。
测试点6-10满足K = 3。

【样例说明】
我们将使用一个由字符D和R组成的字符串来表示Bessie的路线，其中D和R分别表示Bessie向下（down）或向右（right）移动。
第一个子测试用例中，Bessie的两条可能的路线为DDRR和RRDD。
第二个子测试用例中，Bessie的四条可能的路线为DDRR，DRRD，RDDR和RRDD。

第三个子测试用例中，Bessie 的六条可能的路线为DDRR，DRDR，DRRD，RDDR，RDRD和RRDD。
第四个子测试用例中，Bessie的两条可能的路线为DDRR和RRDD。
第五和第六个子测试用例中，Bessie不可能回到牛棚。
第七个子测试用例中，Bessie的六条可能的路线为DDRDRR，DDRRDR，DDRRRD，RRDDDR，RRDDRD和RRDRDD。