在一座新建的科技园中，有一片由 (N \times N) 个方格组成的规划区域。工作人员需要从左上角位于 1,1 位置的控制室出发，前往右下角位于 N,N 位置的中央机房。
为了便于快速抵达目的地，工作人员 只能向右或向下移动。部分位置尚未施工完成，被临时围起，无法通行；其他位置均可自由经过。
工作人员还需要遵守一条特殊限制：在整个行进过程中，最多可以改变前进方向的 K 次。改变方向指的是：从“向右”变为“向下”或从“向下”变为“向右”。(即：在当前一步与上一步方向不同时，路径的起始方向不计入改变方向的次数)
若两条路径中存在至少一个经过的方格不同，则认为它们是不同的路径。
请计算工作人员从控制室到达中央机房一共有多少条合法路径。
第一行输入整数 T，表示测试组数。
每组测试数据格式如下：
接下来输入 N 行，每行一个长度为 N 的字符串。
. 表示该位置可以通过。# 表示该位置被围挡，不可通过。所有数据，保证左上角与右下角均为 .。
输出共 T 行，第 i 行输出第 i 组数据的合法路径数量。
7 3 1 ... ... ... 3 2 ... ... ... 3 3 ... ... ... 3 3 ... .#. ... 3 2 .## ### ##. 3 3 .#. #.. ... 4 3 ...# .#.. .... #...
2 4 6 2 0 0 6
3 5 1 ..... ..... ..... ..... ..... 6 2 ...... ...... ...... ...... ...... ...... 7 3 ....... ....... ...#... ....... ....... ....... .......
2 10 50
5 10 1 .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... 8 2 ........ ........ ...##... ..#..#.. ..#..#.. ...##... ........ ........ 12 1 ............ ............ ............ ............ ............ ............ ............ ............ ............ ............ ............ ............ 10 2 .......... .......... .......... .......... ...#...#.. .......... .......... .......... .......... .......... 11 3 ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ...........
2 6 2 15 182
我们可用由 R（向右）与 D（向下）组成的字符串表示一条路径。
DDRR、RRDD。DDRR、DRRD、RDDR、RRDD。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 |