a와 b로만 이루어진 문자열 s이 있다. 그룹은 같은 글자로 이루어진 가장 긴 연속 부분 문자열이다. 길이가 2 이상인 s의 모든 그룹 g는 제거할 수(뽑을 수) 있고, 남은 왼쪽 부분과 오른쪽 부분을 연결해서 새 문자열을 만들 수 있다. 이러한 과정은 문자열이 빈 문자열이 되거나, 길이가 2 이상인 그룹이 없을 때 까지 계속한다.

예를 들어, s = babbbaaabb일 때, s에는 그룹이 다섯 개 있다. s는 다음과 같은 단계를 거쳐서 빈 문자열로 바꿀 수 있다. (밑 줄이 그어져 있는 그룹이 뽑히는 그룹)

babbbaaabb → baaaabb → bbb → 빈 문자열

하지만, 아래와 같은 단계를 거친다면, 빈 문자열로 바꿀 수 없다.

babbbaaabb → babbbaaa → baaaa → b

문자열이 주어졌을 때, 적절한 과정을 거쳐 빈 문자로 바꿀 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 a와 b로 이루어진 문자열로 이루어져 있다. 문자열의 길이는 1보다 크거나 같고, 25보다 작거나 같다.

출력 형식

각 테스트 케이스에 대해서, 입력으로 주어진 문자열을 빈 문자열로 바꿀 수 있으면 1을, 없으면 0을 출력한다. 

예제 입력

3
babbbaaabb
aabbaabb
abab

예제 출력

1
1
0