Palindrome Coloring

A string is called a palindrome if it reads the same from left to right as it does from right to left. For example, kajak and abba are palindromes.

Adam wrote a string S on a sheet of paper. Gosia wants to color each letter of S so that, for every color, the letters painted with that color form a palindrome when read from left to right (if in doubt, see the examples and the hint below). Your task is to determine the minimum number of colors Gosia needs to achieve this. Adam can only write the first two letters of the alphabet, A and B, so the string S contains no other letters.

The first line contains the number of test cases Z ($1 \le Z \le 10$).

Each test case consists of a single line containing the string S ($1 \le |S| \le 10^5$). S consists only of the characters A and B.

For each test case, print the minimum number of colors Gosia needs, one per line.

In the first example, ABABA is itself a palindrome, so Gosia can color the whole string with a single color.

In the second example, Gosia can color the second letter blue and the rest red. Then the blue letters form the word B and the red letters form the word AABBAA, and both are palindromes.