Problem Description

The cow Bessie is getting ready to go from her favorite pasture back to her barn.

The farm is on an $N \times N$ square grid ($2 \leq N \leq 50$). Her pasture is in the top-left corner, and her barn is in the bottom-right corner. Bessie wants to get home as quickly as possible, so she will only move down or right. Some cells contain haybales, which Bessie cannot pass through, so she must go around them.

Bessie feels a bit tired today, so she wants to change her walking direction at most $K$ times ($1 \leq K \leq 3$).

How many different routes are there for Bessie to go from her favorite pasture to the barn? If one route passes through some cell and another route does not, then the two routes are considered different.

Input Format

The input for each test case contains $T$ subtasks. Each subtask describes a different farm, and all of them must be answered correctly to pass the entire test case. The first line contains $T$ ($1 \leq T \leq 50$). Each subtask is as follows.

The first line of each subtask contains $N$ and $K$.

The next $N$ lines each contain a string of length $N$. Each character is $\texttt{.}$ if the cell is empty, or $\texttt{H}$ if the cell contains a haybale. It is guaranteed that the top-left and bottom-right cells do not contain haybales.

Output Format

Output $T$ lines. The $i$-th line should contain the number of different routes Bessie can choose in the $i$-th subtask.

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

Hint

[Sample Explanation]

We will use a string made of characters D and R to represent Bessie's route, where D and R mean moving down or moving right.

In the first subtask, Bessie's two possible routes are DDRR and RRDD.

In the second subtask, Bessie's four possible routes are DDRR, DRRD, RDDR, and RRDD.

In the third subtask, Bessie's six possible routes are DDRR, DRDR, DRRD, RDDR, RDRD, and RRDD.

In the fourth subtask, Bessie's two possible routes are DDRR and RRDD.

In the fifth and sixth subtasks, it is impossible for Bessie to reach the barn.

In the seventh subtask, Bessie's six possible routes are DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, and RRDRDD.

[Constraints]

• Test points 2 satisfy $K = 1$.
• Test points 3-5 satisfy $K = 2$.
• Test points 6-10 satisfy $K = 3$.

Translated by ChatGPT 5