You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

奶牛 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，这一格中有草堆。输入保证农场的左上角和右下角没有草堆。

输出格式

样例

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

2
4
6
2
0
0
6

提示

【样例解释】

我们将使用一个由字符 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。

【数据范围】

测试点1    满足k=1。

测试点 2-4  满足k=2。

测试点 5-10 满足 k=3。