FRAKTAL - konkurs programistyczny

Malowanie

Drewniany płot ogrodzeniowy u Jasia trzeba koniecznie odrestaurować. Sztachety wyblakły i należy ponownie pokryć je farbą. Jasiu chce zachować liczbę dotychczasowych kolorów sztachet na przęsłach, ale postanowił, że sąsiednie sztachety muszą różnić się barwą. Mógłby malować sztachety na przemian i uzyskałby zamierzony efekt, ale zmiana koloru sztachety na inny powoduje dodatkowe koszty, bo sztachetę taką trzeba malować dwukrotnie. Należy zminimalizować koszty, czyli wyznaczyć najmniejszą liczbę sztachet w przęśle, których barwa zostanie zmieniona na inną, ale taką, która znajdowała się w palecie barw danego przęsła. Wyjątkiem są przęsła zabarwione jednym kolorem, w tym przypadku co druga sztacheta zostanie pomalowana nową barwą.
W celu wyznaczenia sztachet do przebarwienia, Jasiu opisał każde z przęseł za pomocą ciągu dużych liter, gdzie jednakowym literom odpowiada jednakowa barwa, a różnym literom - różna barwa sztachety. Na podstawie tych danych należy wyznaczyć najmniejszą możliwą liczbę sztachet, których barwę należy zmienić.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita p (1 ≤ p ≤ 100) oznaczająca liczbę przęseł płotu. Każde przęsło opisuje w osobnym wierszu ciąg dużych liter alfabetu łacińskiego, którego długość zawiera się w przedziale [1, 10⁶]. Każdej literze ciągu przyporządkowany jest kolor sztachety, gdzie jednakowym literom odpowiada jednakowa barwa. Rozmiar plików wejściowych nie przekracza 5 MB.

Wyjście
Dla każdego ciągu reprezentującego przęsło, należy wypisać najmniejszą liczbę sztachet, które należy przebarwić zgodnie z wytycznymi Jasia.


Przykład

Wejście
5
TOO
ABBA
YYYYY
XXYYZZ
FRAKTAL

Wyjście
1
2
2
3
0

Wyjaśnienie.
Pierwsze przęsło TOO ma trzy sztachety zabarwione dwoma różnymi kolorami. Dwa pierwsze sztachety wystarczy pomalować tym samym kolorem, a kolor ostatniej sztachety należy zmienić na T, aby spełnione zostały warunki. Przęsło drugie ABBA ma cztery sztachety i dwie barwy. Mamy tu dwie kombinacje końcowe, albo ABAB albo BABA, co w obu przypadkach oznacza zmianę barwy dwóch sztachet. Przęsło trzecie to wyjątek, tutaj dobieramy nową barwę minimalnie dla dwóch sztachet i kolorujemy całe przęsło np. na YAYAY. Czwarte przęsło wymaga przebarwienia minimum trzech sztachet, można to zrobić na kilka sposobów, np. XZYXZX. Przęsło FRAKTAL, jak widać, nie potrzebuje zmiany barw sztachet, wystarczy je tylko odświeżyć, malując na ten sam kolor.