Корова Беси идёт с любимого пастбища в амбар.
Пастбище и амбар расположены на решётке n * n, причём пастбище находится в левом верхнем углу, а амбар - в правом нижнем. Беси хочет попасть в амбар как можно быстрее, поэтому она ходит только вниз и вправо. В некоторых ячейках находятся стоги сена, которые Беси должна обходить.
Беси чувствует себя уставшей, поэтому она хочет изменить направление движения не более k раз.
Сколько различных путей имеется у Беси из пастбища в амбар? Два пути считаются различными, если Беси идёт через некоторую ячейку в одном пути и не идёт через неё в другом.
Первая строка содержит t (1 ≤ t ≤ 50) тестов. Каждый тест начинается со строки, содержащей n (2 ≤ n ≤ 50) и k (1 ≤ k ≤ 3).
Каждая из последующих n строк содержит строку из n символов. Каждый символ либо "." если ячейка пуста, или H если в ячейке стог сена. Гарантируется, что левый верхний и правый нижний углы фермы не содержат стоги сена.
Выведите t строк, i-ая тсрока содержит количество различных путей, которыми может пройти Беси для i-го подтеста.
Мы обозначим возможные пути Беси строками из символов D и R, означающих движение вниз и вправо соответственно.
В первом пдтесте у Беси два пути: DDRR и RRDD.
Во втором подтесте у Беси 4 пути: DDRR, DRRD, RDDR, RRDD.
В третьем подтесте у Беси 6 путей: DDRR, DRDR, DRRD, RDDR, RDRD, RRDD.
В четвертом подтесте у Беси 2 пути: DDRR, RRDD.
В 5-ом и 6-ом подтестах беси не может добраться до амбара.
В седьмом подтесте 6 путей DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, RRDRDD.