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

题目描述

给定一个 $n \times n$ 的网格，其中 . 表示空地，H 表示障碍。你要从左上角 $(1,1)$ 走到右下角 $(n,n)$，每一步只能向右或向下移动一格，不能走出网格，也不能进入障碍。

在整条路径中，改变行走方向的次数不能超过 $K$ 次，第一步不计入转向次数。例如路径「右、右、下、下」只转向 $1$ 次。

求满足条件的不同路径的数量。保证起点和终点都不是障碍。

输入格式

第一行输入一个整数 $T$，表示测试组数。

每组数据第一行输入两个整数 $n$ 和 $K$，接下来 $n$ 行每行一个长度为 $n$ 的字符串，描述整个网格。

输出格式

输出 $T$ 行，第 $i$ 行为第 $i$ 组数据的路径数量。

样例 1

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

样例 1 解释

以第 1 组为例：$3 \times 3$ 空网格、$K=1$ 时，只有「右、右、下、下」与「下、下、右、右」两条路径的转向次数不超过 $1$，因此答案为 $2$。

数据范围

• $1 \le T \le 50$；
• $2 \le n \le 50$；
• $1 \le K \le 3$。

本题共 25 个测试点，每个测试点 4 分，按测试点独立计分。每个测试点中，输入文件内所有测试组均满足该测试点的额外限制。