C. Получи четную строку
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка $$$a=a_1a_2\dots a_n$$$ называется чётной, если она состоит из конкатенации (соединения) строк длины $$$2$$$, состоящих из одинаковых символов. Иными словами, строка $$$a$$$ четная, если одновременно выполняются два условия:

  • чётна её длина $$$n$$$;
  • для всех нечётных $$$i$$$ ($$$1 \le i \le n - 1$$$) выполнено $$$a_i = a_{i+1}$$$.

Например, следующие строки являются чётными: «» (пустая строка), «tt», «aabb», «oooo» и «ttrrrroouuuuuuuukk». Следующие строки чётными не являются: «aaa», «abab» и «abba».

Задана строка $$$s$$$, состоящая из строчных латинских букв. Необходимо найти, какое минимальное количество символов нужно удалить из строки $$$s$$$, чтобы она стала четной. Удалённые символы не обязаны идти подряд.

Входные данные

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Каждый набор входных данных состоит из одной строки $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), где $$$|s|$$$ — длина строки $$$s$$$. Строка состоит из строчных букв латинского алфавита.

Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число — минимальное количество символов, которые необходимо удалить, чтобы строка $$$s$$$ стала четной.

Пример
Входные данные
6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw
Выходные данные
3
3
2
0
2
7
Примечание

В первом наборе входных данных можно удалить символы под номерами $$$6$$$, $$$7$$$ и $$$9$$$, получив четную строку «aabbddcc».

Во втором наборе входных данных каждый символ встречается ровно один раз, поэтому для того, чтобы получить четную строку, необходимо удалить все символы из строки.

В третьем наборе входных данных можно получить четную строку «aaaabb», удалив, например, $$$4$$$-й и $$$6$$$-й символы, или строку «aabbbb», удалив $$$5$$$-й символ и любой из первых трех.