Сакурако очень любит чередующиеся строки. Она называет строку \(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
|