Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Разорвать на части
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$, состоящая из строчных латинских букв.

За одно действие вы можете выбрать несколько (одну или больше) позиций в ней так, что никакие две выбранные позиции не соседние друг другу. Затем вы удаляете все буквы на выбранных позициях из строки. Полученные части строки затем склеиваются без изменения порядка.

Какое наименьшее количество действий необходимо совершить, чтобы все буквы в строке $$$s$$$ стали одинаковые?

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

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

В единственной строке каждого набора записана строка $$$s$$$, состоящая из строчных латинских букв. Ее длина от $$$1$$$ до $$$2 \cdot 10^5$$$.

Суммарная длина строк по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul
Выходные данные
1
3
0
2
4
Примечание

В первом наборе входных данных вы можете выбрать позиции $$$2, 4$$$ и $$$6$$$, и удалить соответствующие буквы 'b', 'c' и 'b'.

В третьем примере все буквы в строке уже одинаковые, поэтому не нужно совершать никаких действий.

В четвертом примере одно из возможных решений за $$$2$$$ действия следующее. Сначала выбираете позиции $$$1, 4, 6$$$. Строка становится «bce». Затем выбираете позиции $$$1$$$ и $$$3$$$. Строка становится «c». Все буквы в ней одинаковые, так как это просто одна буква.