Скибидусу дана строка \(s\), состоящая из строчных латинских букв. Пока \(s\) содержит более чем \(1\) букву, он может:
- Выбрать индекс \(i\) (\(1 \leq i \leq |s| - 1\), \(|s|\) обозначает текущую длину \(s\)), такой что \(s_i = s_{i+1}\). Заменить \(s_i\) на любую строчную латинскую букву по своему выбору. Удалить \(s_{i+1}\) из строки.
Скибидус должен определить минимально возможную длину, которую он может достичь за любое количество операций.
Выходные данные
Для каждого набора входных данных выведите целое число на новой строке — минимально достижимую длину \(s\).
Примечание
В первом наборе входных данных Скибидус может:
- Выполнить операцию на \(i = 2\). Он заменяет \(s_2\) на b и удаляет \(s_3\) из строки. Затем \(s\) становится bb.
- Выполнить операцию на \(i = 1\). Он заменяет \(s_1\) на b и удаляет \(s_2\) из строки. Затем \(s\) становится b.
- Поскольку \(s\) содержит только \(1\) букву, Скибидус не может выполнить больше операций.
Таким образом, ответ равен \(1\) для первого набора входных данных.
Во втором наборе входных данных он не может выполнить операцию ни на одном индексе. Поэтому ответ по-прежнему равен длине начальной строки, \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
baa
skibidus
cc
ohio
|
1
8
1
4
|