문자열 뽑기

문자 a와 b로만 이루어진 문자열 $s$가 있다. 그룹은 같은 문자가 연속으로 이어진 가장 긴 부분 문자열을 뜻한다. 길이가 $2$ 이상인 그룹 $g$는 통째로 제거할(뽑을) 수 있으며, 제거한 뒤에는 남은 왼쪽 부분과 오른쪽 부분을 이어 붙여 새로운 문자열을 만든다. 이 과정은 문자열이 빈 문자열이 되거나, 길이가 $2$ 이상인 그룹이 더 이상 남지 않을 때까지 반복한다.

예를 들어 $s =$ babbbaaabb에는 그룹이 다섯 개 있다. 다음과 같이 진행하면 빈 문자열로 만들 수 있다. (굵게 표시된 그룹이 뽑히는 그룹이다.)

babbbaaabb → baaaabb → bbb → 빈 문자열

반면 다음과 같이 진행하면 빈 문자열로 만들 수 없다.

babbbaaabb → babbbaaa → baaaa → b

문자열이 주어졌을 때, 적절한 순서로 그룹을 뽑아 빈 문자열로 만들 수 있는지 판별하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이후 각 줄에 하나씩, a와 b로만 이루어진 문자열이 주어진다. 각 문자열의 길이는 $1$ 이상 $25$ 이하이다.

각 테스트 케이스마다 한 줄에 하나씩, 주어진 문자열을 빈 문자열로 만들 수 있으면 1을, 만들 수 없으면 0을 출력한다.