Minimum Cost to Make String Valid

Given a string containing only '{' and '}', determine the minimum cost required to make the string valid. A string is considered valid if for every opening bracket '{', there is a corresponding closing bracket '}'. You can convert a '{' into '}' or vice versa, with each conversion costing 1.

Example:

The strings "{}{}", "{{}}", and "{{}{}}" are valid, while "}{}", "{}}{{}", and "{{}}}{" are not.

Example:

Input:

STR = "{{"

Output:

1

Explanation:

Converting the '{' at index 1 (0-based) to '}' results in the string "{}", which is valid.

Constraints:

• 1 ≤ T ≤ 100
• 0 ≤ |STR| ≤ 105
• STR[i] = '{' or '}'
• Time Limit: 1 sec

Note:

Return -1 if it is impossible to make 'STR' valid.

Input

The first line contains an integer 'T' representing the number of test cases. Each test case contains a single string 'STR'.

Output

For each test case, output the minimum cost needed to make 'STR' valid. If it is impossible, output -1. Print each result on a new line.