В четвёртом подвиге Рустама, легендарного героя из Шахнаме, старая ведьма создала волшебный лабиринт, чтобы заманить его в ловушку. Лабиринт представляет собой прямоугольную сетку, состоящую из $$$n$$$ строк и $$$m$$$ столбцов. Каждая клетка в лабиринте указывает в определенном направлении: вверх, вниз, влево или вправо. Ведьма заколдовала Рустама так, что всякий раз, когда он находится в клетке, он перемещается в следующую клетку в направлении, указанном этой клеткой.
Если Рустам в конце концов выйдет из лабиринта, он освободится от чар ведьмы и победит ее. Однако, если он будет вечно блуждать по лабиринту, то он останется там навсегда.
Ведьма еще не определила направления для всех клеток. Она хочет назначить направления для неуказанных клеток таким образом, чтобы количество клеток, начав из которых Рустам будет пойман навсегда, было максимальным. Ваша задача — найти это количество.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Для каждого набора входных данных:
- Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 1000$$$), представляющих количество строк и столбцов в лабиринте.
- Каждая из следующих $$$n$$$ строк содержит строку из $$$m$$$ символов, представляющих направления в лабиринте. Каждый символ является одним из следующих:
- U (вверх)
- D (вниз)
- L (влево)
- R (вправо)
- ? (неуказанное направление)
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество клеток, начиная из которых Рустам будет заперт навсегда, после оптимального назначения направлений неопределенным ячейкам.
33 3UUUL?RDDD2 3??????3 3?U?R?LRDL
0 6 5
Назовём плохими клетки, начиная в которых Рустам не сможет выбраться. Остальные клетки назовём хорошими.
В первом наборе входных данных все клетки будут хорошими, независимо от ваших действий.
Во втором наборе входных данных, если вы назначите ? значения, как показано на рисунке ниже, все клетки будут плохими:
В третьем наборе входных данных, если вы назначите ? значения, как показано на рисунке ниже, у вас будет $$$5$$$ плохих клеток (клетки, закрашенные красным):
