题目描述

强哥正准备从她最喜爱的乔斯夏列营营地回到他的老家。

地图是一个 $N \times N$ 的方阵（ $2 ≤ N ≤ 50$ ），其中营地在左上角，强哥老家在右下角。强哥想要尽快回家，所以他只会向下或向右走。有些地方有草堆，强哥无法穿过；他必须绕过它们。

强哥今天感到有些疲倦，所以她希望改变他的行走方向至多 $K$ 次（ $1 ≤ K ≤ 3$ ）。

强哥有多少条不同的路线从营地回到老家的路线？如果一条路线中强哥经过了某个方格而另一条路线中没有，则认为这两条路线不同。

输入格式

每个测试用例的输入包含 $T$ 个子测试用例，每个子测试用例描述了一个不同的地图，并且必须全部回答正确才能通过整个测试用例。输入的第一行包含 $T$ （ $1 ≤ T ≤ 50$ ）。每一个子测试用例如下。

每个子测试用例的第一行包含 $N$ 和 $K$ 。

以下 $N$ 行每行包含一个长为 $N$ 的字符串。每个字符为 . 表示这一格是空的，或 H 表示这一格中有草堆。输入保证地图的左上角和右下角没有草堆。

输出 $T$ 行，第 $i$ 行包含在第 $i$ 个子测试用例中强哥可以选择的不同的路线数量。

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

我们将使用一个由字符 D 和 R 组成的字符串来表示强哥的路线，其中 D 和 R 分别表示强哥向下（down）或向右（right）移动。

第一个子测试用例中，强哥的两条可能的路线为 DDRR 和 RRDD 。

第二个子测试用例中，强哥的四条可能的路线为 DDRR ， DRRD ， RDDR 和 RRDD 。

第三个子测试用例中，强哥的六条可能的路线为 DDRR ， DRDR ， DRRD ， RDDR ， RDRD 和 RRDD 。

第四个子测试用例中，强哥的两条可能的路线为 DDRR 和 RRDD 。

第五和第六个子测试用例中，强哥不可能回到老家。第七个子测试用例中， Bessie 的六条可能的路线为 DDRDRR，DDRRDR，DDRRRD，RRDDDR，RRDDRD和RRDRDD。