Корова Бесі йде з улюбленого пасовища до ферми.

Пасовище і ферма розташовані на решітці \(N \times N\) (\(2 \leq N \leq 50\)), причому пасовище знаходиться в лівому верхньому кутку, а ферма - у правому нижньому. Бесі хоче потрапити до ферми якнайшвидше, тому вона ходить тільки вниз і вправо. У деяких комірках знаходяться стоги сіна, які Бесі має оминати.

Бесі почувається втомленою, тому вона хоче змінити напрямок руху не більше \(K\) разів (\(1 \leq K \leq 3\)).

Скільки різних шляхів є у Бесі з пасовища на ферму? Два шляхи вважаються різними, якщо Бесі йде через деяку комірку в одному шляху і не йде через неї в іншому.

Формат вхідних даних

Введення кожного тесту містить \(T\) підтестів, кожен із яких описує різну ферму і для кожного з яких потрібно видати правильну відповідь, щоб отримати повний бал за тест. Перший рядок введення містить \(T\) (\(1 \leq T \leq 50\)). Далі описується кожен із під-тестів.

Кожен із під-тестів починається з рядка, що містить \(N\) і \(K\).

Кожен з наступних \(N\) рядків містить рядок із \(N\) символів. Кожен символ або \(\texttt{.}\) якщо комірка порожня, або \(\texttt{H}\) якщо в комірці стіг сіна. Гарантується, що лівий верхній та правий нижній кути ферми не містять стоги сіна.

Формат вихідних даних

Виведіть \(T\) рядків, \(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...

Приклад вихідних даних-1

2
4
6
2
0
0
6

Пояснення до прикладу

Ми позначимо можливі шляхи Бесі рядками із символів 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.

Оцінювання

В тесті 2 K=1.
В тестах 3-5 K=2.
В тестах 6-10 K=3.