Taco String Reduction

You are given a string S consisting of lowercase English letters. You must repeatedly perform the following operation: if two adjacent characters in the string are identical, remove them. This process continues until no more adjacent identical characters remain.

Formally, let \(S\) be the given string. While there exists an index \(i\) such that \(S[i] = S[i+1]\), remove both characters and concatenate the remaining parts. Your task is to determine the length of the final string after all such operations have been performed.

Example:

• For \(S = \texttt{abbaca}\): remove "bb" to get \(\texttt{aaca}\), then remove "aa" to get \(\texttt{cc}\), and finally remove "cc" to obtain an empty string. The length of the final string is 0. (Note: Some examples may end with a non-empty string depending on the removal order.)

Note: The removal operation is applied iteratively until no more removals can be made.

inputFormat

The first line of input contains a single integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a non-empty string consisting of lowercase English letters.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing one integer — the length of the resulting string after performing all possible removal operations.

Output should be written to standard output (stdout).

## sample

3
abbaca
aabccba
abacabadabacaba

2
1
15

</p>