Walking Home

Bessie muốn đi từ góc trái trên đến góc phải dưới của lưới $N\times N$. Cô chỉ được đi sang phải (R) hoặc xuống dưới (D). Một số ô bị chặn bởi đống cỏ khô (ký hiệu H).

Bessie muốn đếm số đường đi hợp lệ sao cho số lần đổi hướng không quá $K$ (đổi hướng là khi bước tiếp theo khác hướng bước trước).

Cho $T$ bộ test, với mỗi bộ test hãy tìm số đường đi thỏa mãn.

Dữ liệu vào

• Dòng $1$: Số nguyên $T$ — số bộ test.
• Với mỗi bộ test:
  • Dòng đầu: Hai số nguyên $N$ và $K$.
  • $N$ dòng tiếp theo: Mỗi dòng gồm $N$ ký tự . (trống) hoặc H (bị chặn).

Dữ liệu ra

In $T$ dòng, mỗi dòng là số đường đi hợp lệ của bộ test tương ứng.

Ràng buộc

• $1\le T\le 50$.
• $2\le N\le 50$.
• $1\le K\le 3$.
• Ô $(1,1)$ và $(N,N)$ luôn trống.

Ví dụ