P1031 Mission 2 - E : To the Kingdom of pmurT

Problem Background

From the dialogue, Radar realized that the man in the back is dlanoD pmurT (please try to read it backwards), who is the king of the Kingdom of pmurT (KT). so now Radar is on the way to the country.

But… is there a path to go there?

Problem Statement

Known that now Radar and the country are both in a Rectangular Plane Coordinate System (平面直角坐标系) with Radar\((1,1)\) and the country KT\((N,N)\). That means Radar need to go to \((N,N)\) from \((1,1)\). On the path, there’re some places where Radar can’t go to.

To get to the country ASAP, Radar’s directions will just be up or right and he will only change his direction at most \(K\) times.

So how many different path can Radar go through to get to the country KT?

Constraints

• \(1 \le T \le 50\).
• \(2 \le N \le 50\).
• \(1 \le K \le 3\).

Input

The input for each test case contains \(T\) sub-test cases, each describing a different map and each of which must be answered correctly to pass the full test case. The first line of input contains \(T\). Each of the \(T\) sub-test cases follow.

Each sub-test case starts with a line containing \(N\) and \(K\).

The next \(N\) lines each contain a string of \(N\) characters. Each character is either . if it is okay or H if it can’t be gone to. It is guaranteed \((1,1)\) and \((N,N)\) is always able to be gone to.

Output

Output \(T\) lines, the \(i^{th}\) line containing the number of different paths Radar can take in the \(i^{th}\) sub-test case.

Samples

Input 1

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

Output 1

2
4
6
2
0
0
6