| Codeforces Round 734 (Div. 3) |
|---|
| Закончено |
Это упрощенная версия задачи B2. Возможно, вы захотите сначала ознакомиться с B2 до того как приступить к решению B1.
У Паши и Маши есть любимая строка $$$s$$$, состоящая из строчных букв латинского алфавита. Они захотели её раскрасить с помощью мелков двух цветов: красного и зелёного. Раскраска строки называется чудесной, если выполняются следующие условия:
- каждый символ строки либо закрашивается ровно в один цвет (красный или зелёный), либо не закрашивается вовсе;
- любые два символа, покрашенные в один цвет, различны;
- количество символов, покрашенных в красный цвет, совпадает с количеством символов, покрашенных в зелёный цвет;
- количество покрашенных символов при соблюдении первых трёх условий максимально возможно.
Например, пусть строка $$$s$$$ имеет вид «kzaaa». Одна из её возможных чудесных раскрасок изображена на рисунке.
Пример возможной чудесной раскраски для строки «kzaaa». Паша и Маша хотят сами научиться делать чудесную раскраску строки. Поскольку они очень маленькие, им нужна помощь в виде подсказки. Помогите им найти $$$k$$$ — количество красных (или зелёных, эти числа равны) букв в чудесной раскраске строки.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одной непустой строки $$$s$$$, состоящей из строчных букв латинского алфавита. Количество символов в строке не превышает $$$50$$$.
Для каждого набора входных данных в отдельной строке выведите одно целое неотрицательное число $$$k$$$ — количество символов, которые будут покрашены в красный цвет.
5 kzaaa codeforces archive y xxxxxx
2 5 3 0 1
В первом наборе входных данных содержится строка из условия. Одна из чудесных раскрасок представлена на рисунке. Чудесная раскраска, содержащая $$$3$$$ и более красных букв, не существует, поскольку в таком случае общее количество раскрашенных символов превысит количество символов в строке.
Строку из второго набора входных данных можно раскрасить следующим образом. Первые вхождения букв «c», «o», «e» покрасим в красный цвет, вторые — в зелёный. Буквы «d» и «f» покрасим в красный цвет, «r», «s» — в зелёный. Таким образом, каждый символ будет покрашен либо в красный цвет, либо в зелёный, следовательно, ответа лучше $$$5$$$ не существует.
В третьем наборе входных данных все буквы различны, поэтому в красный цвет можно покрасить любой набор символов, количество которых не превышает половину длины строки и является максимально возможным.
В четвёртом наборе входных данных всего один символ, поэтому, если покрасить его в красный, мы не сможем покрасить какой-либо другой символ в зелёный цвет.
В пятом наборе входных данных все буквы одинаковы, поэтому нельзя покрасить более одного символа в красный цвет.
