Minimum String Length After AB Deletions

You are given t test cases. In each test case, you are given a string consisting only of the lowercase letters a and b. You can perform the following operation any number of times (possibly zero): delete one occurrence of the substring ab from the string. Each deletion simultaneously removes one a and one b that appear consecutively with a preceding b.

Your task is to compute the minimum possible length of the string after performing an arbitrary number of such deletions. It can be shown that the final length is equal to the absolute difference between the number of as and bs in the original string. Formally, if a string has n_a occurrences of a and n_b occurrences of b, then the answer is:

\( | n_a - n_b | \)

Read the input from stdin and output the answer for each test case to stdout, one result per line.

inputFormat

The first line of input contains an integer t (t ≥ 1) representing the number of test cases.

Each of the following t lines contains a single string s consisting only of the characters a and b.

outputFormat

For each test case, output a single line containing the minimum possible length of the string after performing zero or more deletions of the substring ab.

## sample

3
abba
ababab
aaaa

0
0
4

</p>