문제

어떤 단어가 왼쪽에서 오른쪽으로 읽을 때와 거꾸로 읽을 때 똑같이 읽힌다면, 그 단어를 팰린드롬이라 부릅니다. kayak, abba가 대표적 예시입니다.

아담이 단어 S를 씁니다. 고시아는 단어 S의 글자를 여러 색으로 색칠해 같은 색깔로 칠한 글자가 팰린드롬을 이루도록 만들려고 합니다. (이해가 안 될 경우, 예시를 참고합시다.) 당신은 고시아가 목표를 이루기 위해 필요한 최소 색의 개수를 구해야 합니다. 아담은 알파벳의 첫 두 글자 A와 B만 적을 수 있으며, S에는 그 외 다른 글자가 포함되지 않습니다. 

입력

첫 줄에 테스트 케이스의 수 Z가 주어집니다. (1 <= Z <= 10)

하나의 테스트 케이스에는 하나의 줄에 단어 S가 주어집니다. (1 <= S의 길이 <= 10⁵)

출력

각 테스트 케이스에 대해, 고시아가 필요한 최소 색의 수를 출력합니다.