시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 5 4 100.000%

문제

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

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 ).

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

출력

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

예제 입력 1

2
ABABA
ABABBAA

예제 출력 1

1
2

힌트

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

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.