Сакурако очень любит чередующиеся строки. Она называет строку \(s\) из строчных латинских букв чередующейся строкой, если символы на четных позициях одинаковы, если символы на нечетных позициях одинаковы и длина строки четная.
Например, строки 'abab' и 'gg' являются чередующимися, а строки 'aba' и 'ggwp' — нет.
Как хороший друг, вы решили подарить такую строку, но не смогли её найти. К счастью, вы можете выполнить два типа операций над строкой:
- Выберите индекс \(i\) и удалите из строки \(i\)-й символ, что уменьшит длину строки на \(1\). Такую операцию можно выполнить не более \(1\) раза;
- Выберите индекс \(i\) и замените \(s_i\) на любую другую букву.
Поскольку вы торопитесь, вам нужно определить минимальное количество операций, необходимых для превращения строки в чередующуюся.
Выходные данные
Для каждого тестового случая выведите одно целое число — минимальное количество операций, необходимых для превращения строки \(s\) в чередующуюся.
Примечание
Для строки ababa можно удалить первый символ, чтобы получить baba, что является чередующейся строкой.
Для строки acdada можно изменить первые два символа, чтобы получить dadada, что является чередующейся строкой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1
a
2
ca
3
aab
5
ababa
6
acdada
9
ejibmyyju
6
bbccbc
6
abacba
5
bcbca
5
dcbdb
|
1
0
1
1
2
6
2
3
1
1
|