B. Начни с себя
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим конвейер, представляющий собой сетку, состоящую из $$$n$$$ строк и $$$m$$$ столбцов. Ячейка в $$$i$$$-й строке сверху и в $$$j$$$-м слева столбце обозначается как $$$(i,j)$$$.

Каждой ячейке, кроме $$$(n,m)$$$, назначено направление R (вправо) или D (вниз). Если ячейке $$$(i,j)$$$ назначено направление R, любой багаж в ней переместится в ячейку $$$(i,j+1)$$$. Аналогично, если ячейке $$$(i,j)$$$ назначено D, любой багаж в ней переместится в ячейку $$$(i+1,j)$$$. Если в любой момент времени багаж выходит за пределы сетки, он считается утерянным.

В ячейке $$$(n,m)$$$ есть стойка, где подбирается весь багаж. Конвейер называется работоспособным тогда и только тогда, когда любой багаж достигнет стойки, независимо от того, в какую ячейку он изначально помещен. Более формально, для каждой ячейки $$$(i,j)$$$ любой багаж, помещенный в эту ячейку, должен в итоге оказаться в ячейке $$$(n,m)$$$.

Может случиться такое, что это условие изначально не выполняется; вам, однако, разрешено изменять направления некоторых ячеек для обеспечения работоспособности конвейера. Пожалуйста, определите минимальное количество ячеек, направления в которых вы должны изменить.

Обратите внимание, что всегда можно сделать любой конвейер работоспособным, изменив направления набора ячеек.

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

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

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

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов. $$$j$$$-й символ в строке $$$i$$$, $$$a_{i,j}$$$, является начальным направлением ячейки $$$(i, j)$$$. Обратите внимание, что $$$a_{n,m}=$$$ C.

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

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

Пример
Входные данные
4
3 3
RRD
DDR
RRC
1 4
DDDC
6 9
RDDDDDRRR
RRDDRRDDD
RRDRDRRDR
DDDDRDDRR
DRRDRDDDR
DDRDRRDDC
1 1
C
Выходные данные
1
3
9
0
Примечание

В первом случае достаточно просто изменить направление $$$(2,3)$$$ на D.

Вы можете проверить работоспособность полученного конвейера. Например, если мы поместим багаж в $$$(2,2)$$$, он сначала переместится в $$$(3,2)$$$, а затем в $$$(3,3)$$$.

Во втором случае у нас нет другого выбора, кроме как изменить первые $$$3$$$ ячейки с D на R, сделав сетку равной RRRC.