Йду додому
Корова Бесі вирушає з улюбленого пасовища до комори.
Пасовище і комора розташовані на решітці розміром 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.
У п'ятому і шостому тестах Бесі не може дістатися до комори.
У сьомому тесті 6 шляхів: DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, RRDRDD.