E. Расширь маршрут
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана сетка размера $$$n \times n$$$. Строки пронумерованы сверху вниз от $$$1$$$ до $$$n$$$, столбцы пронумерованы слева направо от $$$1$$$ до $$$n$$$.

Робот расположен в клетке $$$(1, 1)$$$. Он может делать два типа ходов:

  • D — перейти на одну клетку вниз;
  • R — перейти на одну клетку вправо.

Роботу запрещено выходить за пределы поля.

Дана последовательность ходов $$$s$$$ — изначальный маршрут робота. Этот маршрут не ведет робота за пределы поля.

Вам разрешено провести произвольное количество изменений строки (возможно, ноль). За одно изменение можно раздвоить один ход в последовательности. То есть, заменить одно вхождение D на DD или одно вхождение R на RR.

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

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора записаны два целых числа $$$n$$$ ($$$2 \le n \le 10^8$$$) — количество строк и столбцов.

Во второй строке каждого набор записана непустая строка $$$s$$$, состоящая только из символов D и R, — изначальный маршрут робота. Этот маршрут не ведет робота за пределы поля.

Суммарная длина строк $$$s$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
3
4
RD
5
DRDRDRDR
3
D
Выходные данные
13
9
3
Примечание

В первом наборе входных данных достаточно рассмотреть следующие измененные маршруты:

  • RD $$$\rightarrow$$$ RRD $$$\rightarrow$$$ RRRD $$$\rightarrow$$$ RRRDD $$$\rightarrow$$$ RRRDDD — этот маршрут посещает клетки $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$ и $$$(4, 4)$$$;
  • RD $$$\rightarrow$$$ RRD $$$\rightarrow$$$ RRDD $$$\rightarrow$$$ RRDDD — этот маршрут посещает клетки $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$ и $$$(4, 3)$$$;
  • RD $$$\rightarrow$$$ RDD $$$\rightarrow$$$ RDDD — этот маршрут посещает клетки $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 2)$$$, $$$(3, 2)$$$ и $$$(4, 2)$$$.

Таким образом, клетки, которые посещены на хотя бы одном измененном маршруте: $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$, $$$(4, 2)$$$, $$$(4, 3)$$$ и $$$(4, 4)$$$.

Во втором примере, нет способа изменить последовательность так, чтобы робот не вышел за пределы поля. Поэтому все посещенные клетки — это те, которые посещены на маршруте DRDRDRDR.

В третьем примере клетки, которые посещены на хотя бы одном измененном маршруте: $$$(1, 1)$$$, $$$(2, 1)$$$ и $$$(3, 1)$$$.

Клетки для всех наборов: