Słowo nazywamy palindromem, jeśli jest takie samo czytane od lewej do prawej jak i wspak. Przykładami palindromów są słowa kajak, abba.</p>

Adam napisał na kartce słowo S. Gosia planuje pokolorować litery słowa S tak, aby litery pokolorowane tym samym kolorem tworzyły palindromy ( w razie wątpliwości spójrz do przykładu i wyjaśnienia przykładu). Twoim zadaniem jest określenie ilu minimalnie kolorów potrzebuje Gosia aby spełnić swój cel. Adam potrafi pisać tylko dwie pierwsze litery alfabetu: A i B, dlatego słowo S nie zawiera innych liter.

입력 형식

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ).</p>

Pojedynczy zestaw testowy składa się z jednej lini, która zawiera słowo S ( 1 <= (długość słowa S) <= 10⁵ ).

출력 형식

Dla każdego zestawu testowego należy wypisać minimalną liczbę kolorów potrzebnych Gosi.

예제 입력

2
ABABA
ABABBAA

예제 출력

1
2

힌트

W teście pierwszym Gosia może pokolorować całe słowo jednym kolorem.</p>

W drugim teście Gosia może pokolorować drugą literę kolorem niebieskim a pozostałe czerwonym. W ten sposób literki niebieskie stworzą słowo "B" a literki czerwone słowo "AABBAA". Oba te słowa są palindromami.