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

题目描述

小 Z 来到了一个迷宫，这个迷宫可以看成是 $n$ 行 $n$ 列的方格图，刚开始小 Z 在迷宫的左上角（第 $1$ 行第 $1$ 列），小 Z 想要走到迷宫的右下角（第 $n$ 行第 $n$ 列）。

具体地，假设第 $i$ 行第 $j$ 列的迷宫用 $a_{i,j}$ 表示，$a_{i,j}$ 只有两种情况：

1. .：表示这个格子是空地可以走
2. H：表示这个格子是障碍物，不可以走

保证起点和终点不会是障碍物。

小 Z 每一步可以向下走或者向右走，并且在整个行走过程中，规定小 Z 的转向次数不能超过 $m$ 次，当然也不能通过障碍物的格子。

问，在满足这些限制下，从起点 $(1,1)$ 到达终点 $(n,n)$ 的方案数是多少？

如果无法到达终点，则输出 $0$。

输入格式

从 maze.in 文件读入数据。

第一行输入一个整数 $t$，表示数据组数。

对于每一组数据，第一行输入两个整数 $n,m$ 分别表示地图大小和转弯的最大次数。

接下来有 $n$ 行，每行输入一个长度为 $n$ 的字符串，表示地图每个格子是空地还是障碍物。

输出格式

输出到 maze.out 文件。

输出有 $t$ 行，每行一个整数表示答案。

样例

4
3 1
...
...
...
3 2
...
...
...
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

2
4
0
6

大样例

点击链接 maze.zip 获取大样例输入数据和输出数据。

说明/提示

样例 1 解释

对于第 $1$ 组数据，因为转向次数最多 $1$ 次，所以小 Z 只有两种方案：

1. 从 $(1,1)$ 向右走到 $(1,3)$，然后转弯，向下走到终点。
2. 从 $(1,1)$ 向下走到 $(3,1)$，然后转弯，向右走到终点。

数据范围

对于 $10\%$ 的数据，$1\le T\le 10, 2\le n\le 5$；

另有 $10\%$ 的数据，$m=1$；

另有 $30\%$ 的数据，$m=2$；

对于 $100\%$ 的数据，$1\le T\le 50, 2\le n\le 50, 0\le m\le 3$。