Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестов $t$ ($1 \le t \le 10^4$). Далее следует описание тестовых случаев.

Первая строка каждого набора входных данных содержит два целых числа $n$ и $m$~ --- высоту и ширину стены ($1 \le n, m$; $n \cdot m \le 10^6$) .

Следующие $n$ строк содержат по $m$ символов, описывающих стену. Занятая ячейка обозначается `\t{\#}', пустая ячейка обозначается `\t{.}'.

Гарантируется, что сумма $n \cdot m$ по всем наборам входных данных не превосходит $10^6$.