Вам дана строка \(s\), состоящая из \(n\) символов. Каждый символ — либо 0, либо 1.
Вы можете проводить операции со строкой. Каждая операция состоит из двух шагов:
- выбрать целое число \(i\) от \(1\) до длины строки \(s\), после чего удалить символ \(s_i\) (длина строки уменьшается на \(1\), номера символов правее удаленного тоже уменьшаются на \(1\));
- если строка \(s\) не является пустой, удалить максимальный по длине префикс, состоящий из одинаковых символов (номера остальных символов и длина строки уменьшаются на длину удаленного префикса).
Обратите внимание, что в каждой операции оба шага обязательны, и их порядок нельзя менять.
Например, если у вас есть строка \(s =\) 111010, первая операция может быть одной из следующих:
- выбрать \(i = 1\): тогда мы получим 111010 \(\rightarrow\) 11010 \(\rightarrow\) 010;
- выбрать \(i = 2\): тогда мы получим 111010 \(\rightarrow\) 11010 \(\rightarrow\) 010;
- выбрать \(i = 3\): тогда мы получим 111010 \(\rightarrow\) 11010 \(\rightarrow\) 010;
- выбрать \(i = 4\): тогда мы получим 111010 \(\rightarrow\) 11110 \(\rightarrow\) 0;
- выбрать \(i = 5\): тогда мы получим 111010 \(\rightarrow\) 11100 \(\rightarrow\) 00;
- выбрать \(i = 6\): тогда мы получим 111010 \(\rightarrow\) 11101 \(\rightarrow\) 01.
Вы заканчиваете проводить операции, когда строка \(s\) становится пустой. Какое максимальное количество операций вы можете провести?
Выходные данные
Для каждого набора входных данных, выведите одно целое число — максимальное количество операций, которые вы можете провести.
Примечание
В первом наборе входных данных, мы можем, например, выбрать \(i = 2\) и получить строку 010 после первой операции. После этого, выбрать \(i = 3\) и получить строку 1. Наконец, мы можем выбрать только \(i = 1\) и получить пустую строку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6
111010
1
0
1
1
2
11
6
101010
|
3
1
1
1
3
|