Description

Bessie the cow is trying to walk from her favorite pasture back to her barn.

The pasture and farm are on an $N \times N$ grid, with herpasture in the top-left corner and the barn in the bottom-right corner. Bessiewants to get home as soon as possible, so she will only walk down and to theright. There are haybales in some locations that Bessie cannot walk through; shemust walk around them.

Bessie is feeling a little tired today, so she wants to change the direction shewalks at most $K$ times .

How many distinct paths can Bessie walk from her favorite pasture to the barn?Two paths are distinct if Bessie walks in a square in one path but not in theother.

• $2 \leq N \leq 50$
• $1 \leq K \leq 3$

Input Format

The input for each test case contains $T$ sub-test cases, each describing adifferent farm and each of which must be answered correctly to pass the fulltest case. The first line of input contains $T$. Each ofthe $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 iseither $\texttt{.}$ if it is empty or $\texttt{H}$ if it has a haybale. It isguaranteed the top-left and bottom-right corners of the farm will not containhaybales.

• $1 \leq T \leq 50$

Output Format

Output $T$ lines, the $i$-th line containing the number of distinct paths Bessiecan take in the $i$-th sub-test case.

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

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

Scoring

• Test case 2 satisfies $K = 1$.
• Test cases 3-5 satisfy $K = 2$.
• Test cases 6-10 satisfy $K = 3$.

Problem Credit

Problem credits: Nick Wu