Вам задана строка \(s\) четной длины \(n\). Строка \(s\) — бинарная, другими словами, состоит только из 0 (нулей) и 1 (единиц).
Строка \(s\) состоит ровно из \(\frac{n}{2}\) нулей и \(\frac{n}{2}\) единиц (\(n\) — четное).
За одну операцию вы можете развернуть любую подстроку \(s\). Подстрока строки — это непрерывная подпоследовательность символов данной строки.
Какое минимальное количество операций вам понадобится, чтобы сделать \(s\) чередующейся? Строка чередующаяся, если \(s_i \neq s_{i + 1}\) для всех \(i\). В общем, существует два типа чередующихся строк: 01010101... или 10101010...
Выходные данные
Для каждого набора входных данных, выведите минимальное количество операций, чтобы сделать \(s\) чередующейся.
Примечание
В первом наборе входных данных, строка 10 уже чередующаяся.
Во втором наборе, мы можем, например, развернуть два последних символа \(s\) и получить: 0110 \(\rightarrow\) 0101.
В третьем наборе, мы можем, например, сделать следующие две операции:
- 11101000 \(\rightarrow\) 10101100;
- 10101100 \(\rightarrow\) 10101010.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
10
4
0110
8
11101000
|
0
1
2
|