Description

huhe又去仙本那了 他又去潜水啦 他要经过这片海域潜到海龟岛上

这片海域是一个N×N 的方阵（2≤N≤50），他的起点是在方阵的左上角，海龟岛在右下角。huhe的技术还不过关，他只会向下或向右潜。有些地方有岩石，huhe 只能绕开。

由于已经玩了很多天，huhe 今天感到有些疲倦，所以他只会改变行走方向至多 K 次（1≤K≤3）。

huhe 有多少条不同的路线到达海龟岛？如果一条路线中 huhe 经过了某个方格的海而另一条路线中没有，则认为这两条路线不同。

Format

Input

每个测试用例的输入包含 T 个子测试用例，每个子测试用例描述了一个不同的海域。 输入的第一行包含 T（1≤T≤50）。每一个子测试用例如下。

每个子测试用例的第一行包含 N 和K。

以下 N 行每行包含一个长为 N 的字符串。每个字符为 .或者H或者空格，空格和H代表岩石。输入保证每片海域的左上角和右下角没有岩石。

Output

每组子测试的路线数目

Samples

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

【样例解释】 使用一个由字符 D 和 R 组成的字符串来表示 huhe 的路线，其中 D 和 R 分别表示 向下（down）或向右（right）移动。

第一个子测试用例中，两条可能的路线为 DDRR 和 RRDD。

第二个子测试用例中，四条可能的路线为 DDRR，DRRD，RDDR 和 RRDD。

第三个子测试用例中，六条可能的路线为 DDRR，DRDR，DRRD，RDDR，RDRD 和RRDD。

第四个子测试用例中，两条可能的路线为 DDRR 和 RRDD。

第五和第六个子测试用例中，不可能到达。

第七个子测试用例中，六条可能的路线为 RRDDRD，DDRDRR，DDRRDR，DDRRRD，RRDDDR 和 RRDRDD。

Limitation

• 测试点 2 满足K=1。
• 测试点 3-5 满足 K=2。
• 测试点 6-10 满足 K=3。