Bricks in the Wall
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боб украшает кирпичом прямоугольную стену в стиле лофт. Стенка состоит из $$$n \times m$$$ ячеек. Некоторые ячейки уже заняты кирпичами, а остальные пустуют.

Боб хочет добавить к этой стене еще два кирпича. Новые кирпичи должны иметь ширину, равную $$$1$$$-й единице, и могут иметь любую положительную длину. Каждый кирпич можно ставить только горизонтально или вертикально, поэтому каждый новый кирпич будет занимать несколько последовательных пустых ячеек в одной строке или в одном столбце. Также эти два кирпича не должны пересекаться, т.е. занимать одну и ту же ячейку.

Какова максимально возможная сумма длин не более чем двух новых кирпичей, которые Боб может добавить к этой стене?

Входные данные

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

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

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

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

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможную сумму длин не более чем двух новых кирпичей.

Пример

Входные данные

    52 2....4 5###.##.....##.##.#.#2 1..2 3####.#5 4##.#..#.#.#.....#.##

Выходные данные

    4
    6
    2
    1
    7