Mr. Seth is very happy as he joined a new school. When he went to the school, he saw many new students around him. Mr. Seth loves to make new friends but he is unable to identify 'good' and 'bad' among them. So an idea came into his mind to generate a random string that comprises lowercase alphabets such that it counts the number of good and bad friends.

As Mr. Seth is very weak at identifying 'good' and 'bad', so he provides you the string and asks you to find the number of 'good' and 'bad' that can be generated using characters of S such that his friend circle is balanced. Friend circle is balanced when the given string can generate good friends more than or equal to bad friends.

Help Mr. Seth in finding the maximum balance factor (good - bad) of Mr Seth's friend circle.

Input

The first line of input consists of an integer T, describing the number of test cases.
The only line of T test case has a string S, generated by Mr. Seth.

Output

Print the maximum balance factor of Mr Seth friend circle or -1 if it is unbalance.

Constraints

1 <= T <= 100
1 <= |S| <= 10⁵