Poprawne nawiasowanie

Limit czasu: 2s | Limit pamięci: 64MB

Nawiasowaniem nazwiemy napis złożony ze znaków nawiasów (()[]{}).

Poprawnym nawiasowaniem nazwiemy takie nawiasowanie, które mogło powstać poprzez usunięcie z pewnego poprawnego wyrażenia matematycznego wszystkich znaków poza nawiasami.

Ciekawa jest też rekurencyjna definicja poprawnego nawiasowania: Pusty napis jest poprawnym nawiasowaniem. Jeżeli $s_1$ i $s_2$ są pewnymi poprawnymi nawiasowaniami, to wtedy poprawnymi nawiasowaniami są także napisy:

• $s_1s_2$,
• $(s_1)$,
• $[s_1]$,
• $\{s_1\}$.

Dane jest pewne nawiasowanie $s$. Sprawdź czy jest ono poprawne.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę przypadków testowych $t$. Następne $t$ wierszy zawiera opisy przypadków testowych. Każdy przypadek testowy składa się z jednego nawiasowania $s$.

Wyjście

W kolejnych wierszach wyjścia powinny znajdować się odpowiedzi na kolejen przypadki testowe – pojedyncze słwo TAK, jeżeli $s$ jest poprawnym nawiasowanie lub NIE, jeżeli $s$ nie jest poprawnym nawiasowaniem.

Ograniczenia

• $1 \le |s| \le 10^6$
• Suma $|s|$ po wszystkich przypadkach testowych nie przekroczy $10^7$
• W testach wartych łącznie $50\%$ punktów $s$ składa się tylko z nawiasów okrągłych (())

Przykłady

Wejście 1

3
(()())()
())
())(()

Wyjście 1

TAK
NIE
NIE

Wejście 2

3
([]){}
(]
[()(])

Wyjście 2

TAK
NIE
NIE