Корова Беси идёт с любимого пастбища в амбар.

Пастбище и амбар расположены на решётке 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.