DFS
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <iostream>
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; inc = -~inc)
using namespace std;
const int N = 5E1 + 5E0;
inline int fast_read(void) {
int n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
int t, n, k;
char board[N][N];
inline void print_board(void) {
putchar(10);
f(y, 1, n + 1) f(x, 1, n + 1) printf("%c%c", *(*(board + y) + x), x == n ? 10 : 0);
}
constexpr int dirs[][2] {1, 0, 0, 1};
inline int DFS(int x, int y, int d, int c) {
if (x == n and y == n) return 1;
int cnts = 0, nx, ny;
f(i, 0, 2) {
nx = x + **(dirs + i), ny = y + *(*(dirs + i) + 1);
if (nx < 1 or ny < 1 or nx > n or ny > n or
*(*(board + ny) + nx) == 'H' or c + (d != i) > k) continue;
cnts += DFS(nx, ny, i, c + (d != i));
}
return cnts;
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
t = r();
while (t--) {
n = r(), k = r();
f(y, 1, n + 1) f(x, 1, n + 1) cin >> *(*(board + y) + x);
// print_board();
printf("%d\n", DFS(1, 1, -1, -1));
}
// fclose(stdin);
return ~~(0 ^ 0);
}