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

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

Вы можете выполнить следующую операцию со строкой $$$s$$$: выберите подстроку (возможно, пустую) строки $$$s$$$ и перемешайте её (переупорядочите символы в подстроке по своему усмотрению).

Напомним, что палиндром — это строка, которая читается одинаково с первого символа до последнего и с последнего символа до первого. Например, строки a, bab, acca, bcabcbacb являются палиндромами, но строки ab, abbbaa, cccb — нет.

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

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

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

Единственная строка каждого набора входных данных содержит строку $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$), состоящую из строчных латинских букв.

Дополнительные ограничения на входные данные:

  • строка $$$s$$$ имеет четную длину;
  • строку $$$s$$$ всегда можно преобразовать в палиндром;
  • сумма длин строк $$$s$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Выходные данные

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

Пример
Входные данные
4
baba
cc
ddaa
acbacddacbca
Выходные данные
2
0
3
2
Примечание

В первом примере вы можете выполнить операцию следующим образом: baba $$$\rightarrow$$$ baab.

Во втором примере строка уже является палиндромом, поэтому мы можем перемешать пустую подстроку.

В третьем примере вы можете выполнить операцию следующим образом: ddaa $$$\rightarrow$$$ adda.

В четвертом примере вы можете выполнить операцию следующим образом: acbacddacbca $$$\rightarrow$$$ acbcaddacbca.