Shortest Length After Adjacent Pair Removals

You are given T test cases. For each test case, you are given a string S. Your task is to repeatedly remove any pair of adjacent identical characters from the string until no such pair exists.

Formally, if at any step the string S contains two consecutive characters S[i] and S[i+1] with S[i] = S[i+1], remove these two characters from the string. This removal operation is repeated until there is no possible adjacent pair to remove.

Mathematically, if S = a_1a_2\cdots a_n, then whenever a_i = a_{i+1}, these characters are removed. The final answer is the length of the string after all removals.

For example, given the string "abbac":
Step 1: "a bb ac" becomes "aac" after removing the adjacent "bb".
Step 2: "aa c" becomes "c" after removing the adjacent "aa".
The final length is 1.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer T, denoting the number of test cases.
• The next T lines each contain a string S.

Each string consists of characters and may be empty.

outputFormat

For each test case, output one integer on a separate line representing the length of the string after all adjacent identical pairs have been removed.

The output is written to standard output (stdout).

## sample

3
abbac
abcde
aa

1
5
0

</p>