회문 색칠

어떤 문자열을 왼쪽에서 오른쪽으로 읽으나 오른쪽에서 왼쪽으로 읽으나 똑같다면, 그 문자열을 회문(palindrome)이라고 부른다. 예를 들어 kajak, abba는 회문이다.

아담이 종이에 문자열 S를 적었다. 고시아는 S의 각 글자를 색칠하려고 하는데, 같은 색으로 칠해진 글자들을 왼쪽에서 오른쪽 순서대로 이어 붙이면 회문이 되어야 한다(헷갈리면 아래 예제와 힌트를 참고하라). 고시아가 이 목표를 이루기 위해 필요한 색의 최소 개수를 구하여라. 아담은 알파벳의 처음 두 글자인 A와 B만 쓸 수 있으므로, 문자열 S에는 이 두 글자 외의 다른 글자가 없다.

첫째 줄에 테스트 케이스의 개수 Z가 주어진다 ($1 \le Z \le 10$).

각 테스트 케이스는 한 줄로 이루어지며, 그 줄에 문자열 S가 주어진다 ($1 \le |S| \le 10^5$). S는 A와 B로만 이루어져 있다.

각 테스트 케이스마다 고시아에게 필요한 색의 최소 개수를 한 줄에 하나씩 출력한다.

첫 번째 예제에서 ABABA는 그 자체로 회문이므로, 고시아는 문자열 전체를 한 가지 색으로 칠할 수 있다.

두 번째 예제에서 고시아는 두 번째 글자를 파란색으로, 나머지를 빨간색으로 칠할 수 있다. 그러면 파란색 글자는 B, 빨간색 글자는 AABBAA가 되고, 둘 다 회문이다.