집으로 걷기

젖소 Bessie는 가장 좋아하는 목초지에서 헛간으로 걸어 돌아가려고 한다.

목초지와 농장은 $N \times N$ 격자에 있고($2 \leq N \leq 50$), 목초지는 왼쪽 위 모서리에, 헛간은 오른쪽 아래 모서리에 있다. Bessie는 최대한 빨리 집에 가고 싶어서 아래쪽과 오른쪽으로만 걷는다. 일부 위치에는 건초더미가 있어 지나갈 수 없고, Bessie는 그 주위로 돌아가야 한다.

Bessie는 오늘 조금 피곤해서 걷는 방향을 최대 $K$번 바꾸려고 한다($1 \leq K \leq 3$).

Bessie가 가장 좋아하는 목초지에서 헛간까지 걸을 수 있는 서로 다른 경로는 몇 개인가? 한 경로에서 어떤 칸을 지나가고 다른 경로에서는 지나가지 않으면 두 경로는 서로 다르다.

각 테스트 케이스의 입력은 $T$개의 부분 테스트 케이스를 포함하며, 각각 서로 다른 농장을 나타내고, 전체 테스트 케이스를 통과하려면 모든 부분 테스트 케이스를 올바르게 답해야 한다. 입력의 첫째 줄에 $T$가 주어진다($1 \leq T \leq 50$). 이어서 $T$개의 부분 테스트 케이스가 주어진다.

각 부분 테스트 케이스의 첫째 줄에는 $N$과 $K$가 주어진다.

다음 $N$개의 줄에는 각각 $N$개의 문자로 이루어진 문자열이 주어진다. 각 문자는 빈 칸이면 ., 건초더미가 있으면 H이다. 농장의 왼쪽 위 모서리와 오른쪽 아래 모서리에는 건초더미가 없다.

$T$개의 줄을 출력하고, $i$번째 줄에는 $i$번째 부분 테스트 케이스에서 Bessie가 지날 수 있는 서로 다른 경로의 수를 출력한다.