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

Назовем левым циклическим сдвигом некоторой строки $$$t_1 t_2 t_3 \dots t_{n - 1} t_n$$$ следующую строку: $$$t_2 t_3 \dots t_{n - 1} t_n t_1$$$.

Аналогично, назовем правым циклическим сдвигом строки $$$t$$$ строку $$$t_n t_1 t_2 t_3 \dots t_{n - 1}$$$.

Скажем, что строка $$$t$$$ является хорошей, если ее левый циклический сдвиг равен правому циклическому сдвигу.

Вам дана строка $$$s$$$, состоящая из цифр 09.

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

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

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Следующие $$$t$$$ строк содержат описание наборов входных данных. Первая и единственная строка каждого набора содержит строку $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$). Каждый символ $$$s_i$$$ является цифрой 09.

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

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

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

Пример
Входные данные
3
95831
100120013
252525252525
Выходные данные
3
5
0
Примечание

В первом примере можно стереть любые $$$3$$$ символа, например $$$1$$$-й, $$$3$$$-й и $$$4$$$-й. Вы получите строку 51, и это хорошая строка.

Во втором примере можно стереть все символы, кроме 0: оставшаяся строка 0000 — хорошая.

В третьем примере заданная строка $$$s$$$ уже является хорошей.