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

题目描述

一个 $n\times n$ 的方格图，其中 $.$ 代表空地， $h$ 代表障碍。

$WDG$ 希望从图的左上走到右下，每次只能向下或向右走，如果碰到障碍，则必须绕过。

由于 $WDG$ 本身不擅长转向，规定在整个过程中，转向次数不能超过 $m$ 次（ $m<=3$ ），问在这些限制下，从左上走到右下，有多少种不同的走法。

输入格式

本题包含多组测试数据。第一行输入一个数T，表示测试组数。 之后对于每组测试，第一行包含 n 和 m。其中n是方格图的大小，m是转向次数。 后面是一个n*n的方格图，其中.代表空地，可以随意穿行，H代表障碍。 其中1≤T≤50，2≤n≤50，0≤m≤3。

输出格式

输出 T 行，对应 T 个测试的答案

数据范围

对于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 5$。

输入样例

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

输出样例

2
4
0
6