Evalúa expresiones con enteros no negativos, sumas, restas y paréntesis, sin usar funciones como eval. Puede haber espacios en cualquier parte (salvo dentro de un número). El signo - también puede ser unario, al comienzo de la expresión o justo después de (, como en -(2 + 3) o (-4); el + nunca es unario.

Entrada

La primera línea tiene \(T\) y siguen \(T\) líneas con una expresión válida cada una. Los números tienen a lo más \(7\) dígitos y la suma de los largos de las líneas es a lo más \(3 \cdot 10^5\). Los paréntesis pueden anidarse hasta \(5000\) niveles, y todo resultado intermedio cabe en un entero de 64 bits.

Salida

Para cada expresión, su valor.

Ejemplo 1

Entrada

3
1 + 1
 2-1 + 2 
(1+(4+5+2)-3)-(6+8)

Salida

2
3
-5

Ejemplo 2

Entrada

2
-(2 + 3)
- (3 + (4 + 5))

Salida

-5
-12

Basado en el problema 224 de LeetCode, Basic Calculator, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.