Михаил ходит по 2D плоскости. Он может двигаться вправо или вверх. Вам задана последовательность ходов Михаила. Он думает, что эта последовательность слишком длинная, и хочет сделать её настолько короткой, насколько можно.
В заданной последовательности ход вверх обозначается символом U, а ход вправо — символом R. Михаил может заменять пары подряд идущих ходов RU и UR на ходы по диагонали. Это означает, что он может заменять два хода (вверх и вправо) на один (по диагонали). После этого он может сделать ещё замену, пока из последовательности не пропадут подстроки RU и UR.
Ваша задача вывести минимально возможную длину короткой последовательности ходов после всех замен.
Выходные данные
Выведите минимально возможную длину короткой последовательности ходов после всех замен.
Примечание
В первом тесте короткая последовательность ходов может быть DUD (её длина равна 3).
Во втором тесте короткая последовательность ходов может быть UUDRRRDUDDUUU (её длина равна 13).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
RUURU
|
3
|
|
2
|
17
UUURRRRRUUURURUUU
|
13
|