Корова Беси идёт с любимого пастбища в амбар.
Пастбище и амбар расположены на решётке \(N \times N\) (\(2 \leq N \leq 50\)),
причём пастбище находится в левом верхнем углу, а амбар - в правом нижнем.
Беси хочет попасть в амбар как можно быстрее, поэтому она ходит только вниз и вправо.
В некоторых ячейках находятся стоги сена, которые Беси должна обходить.
Беси чувствует себя уставшей, поэтому она хочет изменить направление движения
не более \(K\) раз (\(1 \leq K \leq 3\)).
Сколько различных путей имеется у Беси из пастбища в амбар?
Два пути считаются различными, если Беси идёт через некоторую ячейку в одном пути
и не идёт через неё в другом.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Ввод для каждого теста содержит
\(T\) подтестов, каждый из которых описывает
различную ферму и для каждого из которых нужно выдать правильный ответ, чтобы
получить полный балл за тест. Первая строка ввода содержит
\(T\) (
\(1 \leq T \leq 50\)).
Далее описывается каждый из под-тестов.
Каждый из под-тестов начинается со строки, содержащей \(N\) и \(K\).
Каждая из последующих \(N\) строк содержит строку из \(N\) символов.
Каждый символ либо \(\texttt{.}\) если ячейка пуста, или \(\texttt{H}\) если в ячейке
стог сена. Гарантируется, что левый верхний и правый нижний углы фермы не содержат
стоги сена.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\) строк, \(i\)-ая тсрока содержит количество различных путей,
которыми может пройти Беси для \(i\)-го подтеста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|