Maximum Depth of Parentheses

Given a string (s) that may contain letters, digits, and parentheses, determine the maximum depth of nested parentheses. The depth is defined as the maximum number of open parentheses at any point in the string. For example, the string (a(b)c) has a depth of 2, and the string ((())) has a depth of 3. If no parentheses are present, the depth is 0. Assume that the input string is well-formed; that is, every opening parenthesis has a corresponding closing parenthesis.

inputFormat

The first line contains a positive integer (T), representing the number of test cases. Each of the following (T) lines consists of a string (s) which may contain letters, digits, and parentheses.

outputFormat

For each test case, output a single integer denoting the maximum depth of nested parentheses in the string. Each result should be printed on a new line.## sample

4
(a(b)c)
((a+b)*(c/d))
xyz
()((())())

2
2
0
3