Popping Groups

You are given a string $s$ consisting only of the characters a and b. A group is a maximal run of consecutive identical characters. Any group $g$ whose length is at least $2$ can be removed (popped) in its entirety; after removing it, the remaining left part and right part are concatenated into a new string. Repeat this process until the string becomes empty or no group of length at least $2$ remains.

For example, $s =$ babbbaaabb has five groups. You can turn it into the empty string as follows (the group in bold is the one being popped):

babbbaaabb → baaaabb → bbb → empty string

However, the following order fails to reach the empty string:

babbbaaabb → babbbaaa → baaaa → b

Given a string, write a program that decides whether it can be reduced to the empty string by popping groups in a suitable order.

The first line contains the number of test cases $T$. Each of the following lines contains one string made up of a and b. Each string has length between $1$ and $25$ inclusive.

For each test case, print 1 if the given string can be reduced to the empty string, or 0 otherwise, one per line.