Longest Equal Substring

Given a string s consisting only of characters 'a' and 'b', your task is to find the length of the longest contiguous substring in which the number of 'a's is equal to the number of 'b's.

You are required to solve this problem by computing a balance value for the string and using an efficient method (e.g., prefix sum technique) to determine the longest balanced segment. In mathematical notation, you are to find the maximum l such that there exists indices i and j satisfying:

[ \text{balance}(j) - \text{balance}(i-1) = 0 ]

where the balance function increases by 1 for an 'a' and decreases by 1 for a 'b'.

If no such substring exists, output 0.

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 non-empty string s consisting only of the characters 'a' and 'b'.

outputFormat

For each test case, output a single integer on a new line which is the length of the longest substring with an equal number of 'a's and 'b's.

## sample

3
abba
aaaa
aababab

4
0
6

</p>