У Shubham есть бинарная строка \(s\). Бинарная строка — это строка, содержащая только символы «0» и «1».
Он может выполнить следующую операцию над строкой любое количество раз:
- Выбрать индекс строки, и поменять символ с этим индексом. Это означает, что если символ был «0», он становится «1», и наоборот.
Строка называется хорошей, если она не содержит строк «010» или «101» в качестве подпоследовательностей — например, «1001» содержит «101» как подпоследовательность, следовательно, это не хорошая строка, а «1000» не содержит ни «010» ни «101» как подпоследовательностей, поэтому это хорошая строка.
Какое минимальное количество операций ему придется выполнить, чтобы строка стала хорошей? Можно показать, что с помощью данных операций можно сделать любую строку хорошей.
Строка \(a\) является подпоследовательностью строки \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов.
Выходные данные
Для каждой строки выведите минимальное количество операций необходимых для того, чтобы сделать ее хорошей.
Примечание
В наборах входных данных \(1\), \(2\), \(5\), \(6\) строки уже являются хорошими — поэтому никаких операций не требуется.
Для набора \(3\): «001» можно получить, поменяв первый символ, и это один из возможных способов получить хорошую строку.
Для набора \(4\): «000» можно получить, поменяв второй символ, и это один из возможных способов получить хорошую строку.
Для набора \(7\): «000000» можно получить, поменяв третий и четвертый символы, и это один из возможных способов получить хорошую строку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
001
100
101
010
0
1
001100
|
0
0
1
1
0
0
2
|