Вася и Петя придумали новую игру. Вася берет полоску 1 × n клеточек, и раскрашивает ее клетки в белый и черный. После этого Петя может делать ходы — за один ход он может выбрать любые две соседние клетки одного цвета и перекрасить эти две клетки так, как ему захочется, возможно в разные цвета. Петя может перекрашивать клетки только в белый и черный. Цель Пети — перекрасить полоску так, чтобы никакие две соседние клетки не были одного цвета. Помогите Пете — по заданной начальной раскраске найдите наименьшее количество ходов, необходимое Пете чтобы выиграть.
Выходные данные
Если Петя не сможет выиграть при такой начальной раскраске, выведите -1. Иначе выведите наименьшее число ходов, необходимое Пете для победы.
Примечание
В первом примере Петя может выбрать клетки 1 и 2. Он перекрашивает клетку 1 в черный и клетку 2 в белый.
Во втором примере Петя может выбрать клетки 2 и 3. Он перекрашивает клетку 2 в белый и клетку 3 в черный.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
111010
|
1
|
|
2
|
5
10001
|
1
|
|
3
|
7
1100010
|
2
|
|
4
|
5
00100
|
2
|