El desafortunado Willy tuvo muchos problemas para llegar a tiempo a su exámen final de "algoritmos", este curso le gusta mucho a Willy, sin embargo solo le quedan 10 minutos para dar el exámen de 10 problemas. El profesor de Willy es conciente de la capacidad de su alumno, asi que propone a Willy un problema que no se ha propuesto en el exámen y que cuya solución correcta sería suficiente para aprobar el exámen. Willy no puede evaluar opciones y acepta el reto.

El nuevo problema consiste en un cadena que contiene solo caracteres "(" y ")". Willy debe determinar si la cadena corresponde a una secuencia regular. Una secuencia se llama regular si es posible obtener una expresión aritmética correcta mediante la inserción de caracteres « + » y « 1 » en esta secuencia.

Por ejemplo, las secuencias « ( ( ) ) ( ) », « ( ) » y « ( ( ) ( ( ) ) ) » son regulares, mientras que « ) ( », « ( ( ) » y « ( ( ) ) ) ( » no lo son. La pregunta para Willy es: ¿Cuál es la longitud máxima de una secuencia regular que se puede obtener de la cadena?.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La única línea de un caso consiste en una cadena no vacía de « ( » y « ) » caracteres y su longitud no exceda de 10000.

Output

Salida para cada caso, la longitud máxima posible de una secuencia regular.

Entrada de ejemplo