题目描述

给定 $T$ 个 $N\times N$ 的网格。. 表示可以通行，# 表示障碍。从左上角 (1,1) 出发，只能向右或向下移动，目标是到达右下角 (N,N)。一条路径中改变移动方向的次数不能超过 $K$，起始方向不计作改变方向。请求出合法路径数量。

输入格式

第一行包含整数 $T$。 每组数据的第一行包含两个整数 $N,K$，接下来 $N$ 行每行包含长度为 $N$ 的网格字符串。

输出格式

输出 $T$ 行，每行一个整数，表示对应网格的合法路径数量。

样例

2
3 1
...
...
...
3 2
...
...
...

2
4

数据范围与提示

• $1 \le T \le 50$
• $2 \le N \le 50$
• $1 \le K \le 3$
• 左上角和右下角均为 .。