Робот Кельвин находится на бесконечном клетчатом поле. Его исходный код является последовательностью из n команд, каждая из которых это «U», «R», «D», или «L» — указание роботу сдвинуться на одну клетку вверх, вправо, вниз или влево соответственно. Кельвину интересно, сколько различных подстрок (непрерывных подпоследовательностей) строки с командами обладают тем свойством, что, выполнив все команды данной подстроки, Кельвин вернётся в ту же клетку, с которой начинал. Две подстроки считаются различными, если у них отличаются индексы первой или последней позиции.
Выходные данные
Выведите единственное целое число — количество подстрок, выполнение которых оставит Кельвина на месте.
Примечание
В первом примере подходит вся строка и подстрока «RL».
Обратите внимание: в третьем примере подстрока «LR» встречается три раза, поэтому и в ответе должна быть учтена тоже три раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
URLLDR
|
2
|
|
2
|
4
DLUU
|
0
|
|
3
|
7
RLRLRLR
|
12
|