题目描述

在一座新建的科技园中，有一片由 ($N \times N$) 个方格组成的规划区域。工作人员需要从左上角位于 $(1, 1)$ 位置的控制室出发，前往右下角位于 $(N, N)$ 位置的中央机房。

为了便于快速抵达目的地，工作人员只能向右或向下移动。部分位置尚未施工完成，被临时围起，无法通行；其他位置均可自由经过。

工作人员还需要遵守一条特殊限制：在整个行进过程中，最多可以改变前进方向的 $K$ 次。改变方向指的是：从"向右"变为"向下"或从"向下"变为"向右"。(即：在当前一步与上一步方向不同时，路径的起始方向不计入改变方向的次数)

若两条路径中存在至少一个经过的方格不同，则认为它们是不同的路径。

请计算工作人员从控制室到达中央机房一共有多少条合法路径。

输入格式

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

每组测试数据格式如下：

• 第一行输入两个整数 $N$ 和 $K$。
• 接下来输入 $N$ 行，每行一个长度为 $N$ 的字符串。
  • . 表示该位置可以通过。
  • # 表示该位置被围挡，不可通过。

所有数据，保证左上角与右下角均为 .。

输出格式

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

样例 #1

输入

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.#.
...
3 2
.##
###
##.
3 3
.#.
#..
...
4 3
...#
.#..
....
#...

输出

2
4
6
2
0
0
6

样例 #2

输入

3
5 1
.....
.....
.....
.....
.....
6 2
......
......
......
......
......
......
7 3
.......
.......
...#...
.......
.......
.......
.......

输出

2
10
50

样例 #3

输入

5
10 1
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
8 2
........
........
...##...
..#..#..
..#..#..
...##...
........
........
12 1
............
............
............
............
............
............
............
............
............
............
............
............
10 2
..........
..........
..........
..........
...#...#..
..........
..........
..........
..........
..........
11 3
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........
...........

输出

2
6
2
15
182

样例说明

样例 1 说明

我们可用由 R（向右）与 D（向下）组成的字符串表示一条路径。

• 第 1 组样例共有两条路径：DDRR、RRDD。
• 第 2 组样例共有四条路径：DDRR、DRRD、RDDR、RRDD。
• 第 3 组样例共有六条路径。
• 第 4 组样例中间位置被围挡，只剩两条路径可行。
• 第 5 与第 6 组样例由于阻挡布局，无法抵达终点。
• 第 7 组样例共有六条路径，如 DDRDRR、RRDDRD 等。

数据范围

对于 $100\%$ 的数据，满足 $2 \le N \le 50$，$1 \le K \le 3$，$1 \le T \le 50$。

测试点编号	$K$
$1 \sim 2$	$K = 1$
$3 \sim 5$	$K = 2$
$6 \sim 10$	$K = 3$