Un texto formado solo por los caracteres (, ), [, ], { y } es válido si cada símbolo que abre se cierra con uno del mismo tipo, en el orden correcto: lo último que se abrió es lo primero que se cierra. Por ejemplo, ([]{}) es válido, pero (] y ([)] no lo son.

Para cada texto, di si es válido.

Entrada

La primera línea tiene \(T\), la cantidad de textos. Cada una de las siguientes \(T\) líneas tiene un texto no vacío de esos seis caracteres. La suma de los largos es a lo más \(2 \cdot 10^5\).

Salida

Para cada texto, una línea con true si es válido o false si no.

Ejemplo 1

Entrada

4
()
()[]{}
(]
([)]

Salida

true
true
false
false

Ejemplo 2

Entrada

3
{[]}
((
)(

Salida

true
false
false

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