暂无测试数据。

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

农场位于一个 $N\times N$ 的方阵上（$2\leq N\leq 50$），其中她的草地在左上角，牛棚在右下角。Bessie 想要尽快回家，所以她只会向下或向右走。有些地方有草堆（haybale），Bessie 无法穿过；她必须绕过它们。

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

Bessie 有多少条不同的从她最爱的草地回到牛棚的路线？如果一条路线中 Bessie 经过了某个方格而另一条路线中没有，则认为这两条路线不同。

输入格式

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

每个子测试用例的第一行包含 $N$ 和 $K$。以下 $N$ 行每行包含一个长为 $N$ 的字符串。每个字符为 .，如果这一格是空的，或 H，如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。

输出格式

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

数据范围

• 测试点 $2$ 满足 $K=1$。
• 测试点 $3\sim 5$ 满足 $K=2$。
• 测试点 $6\sim 10$ 满足 $K=3$。

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