时间限制：1秒　　内存限制：256M

---

【问题描述】

　　奶牛贝茜正准备从她最喜爱的草地回到她的牛棚。

　　农场位于一个 \(N×N\) 的方阵上，其中她的草地在左上角，牛棚在右下角。贝茜 想要尽快回家，所以她只会向下或向右走。有些地方有草堆，贝茜无法穿过；她必须绕过它们。

　　贝茜今天感到有些疲倦，所以她希望改变她的行走方向至多 \(K\) 次 \(（1≤K≤10）\)。

　　贝茜有多少条不同的回到牛家的路线？如果一条路线中贝茜经过了某个方格而另一条路线中没有，则认为这两条路线不同。

【输入格式】

　　每个测试用例的输入包含 \(T\) 组数据，每组数据描述了一个不同的农场。
　　输入的第一行包含 \(T（1≤T≤50）\)。每一组数据如下。
　　每组数据的第一行包含 \(N\) 和 \(K\)。
　　以下 \(N\) 行每行包含一个长为 \(N\) 的字符串。每个字符为'.'，如果这一格是空的，或 'H'，如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。

【输出格式】

　　输出 \(T\) 行，第 \(i\) 行包含在第 \(i\) 组数据中 贝茜 可以选择的不同的路线数量。

【输入输出样例】

　Input

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

　Output

2
4
6
2
0
0
6

【样例说明】

　　我们将使用一个由字符 D 和 R 组成的字符串来表示 贝茜 的路线，其中 D 和 R 分别表示 贝茜 向下（down）或向右（right）移动。
　　第一个组数据中，贝茜的两条可能路线为 DDRR 和 RRDD。
　　第二个组数据中，贝茜的四条可能路线为 DDRR，DRRD，RDDR 和 RRDD。
　　第三个组数据中，贝茜的六条可能路线为 DDRR，DRDR，DRRD，RDDR，RDRD，RRDD。
　　第四个组数据中，贝茜的两条可能路线为 DDRR 和 RRDD。
　　第五和第六个组数据中，贝茜 不可能回到牛棚。
　　第七个组数据中，贝茜的六条可能路线为 DDRDRR，DDRRDR，DDRRRD，RRDDDR，RRDDRD 和 RRDRDD。

【数据说明】

　　测试点 2 满足 \(2≤N≤50，K=1\)。
　　测试点 3-5 满足 \(2≤N≤50，K=2\)。
　　测试点 6-10 满足 \(2≤N≤50，K=3\)。
　　测试点 11-15 满足 \(2≤N≤50，K≤10\)。

【来源】

　　Mr.he