Erai in camera ta, iti vedeai de treaba ta, treceai Trie-ul persistent in documentatia pentru Finala ACM. Deodata, bate cineva la usa. Vecinul de alaturi te roaga sa-i imprumuti doua parantezari corecte, pentru ca are niste prieteni in vizita si ar vrea sa joace un joc. Fiindca nu are o parere foarte buna despre tine, el iti ofera o definitie recursiva a corectitudinii unui sir de paranteze, in speranta ca o poti urmari:

- Sirul "()" este corect.

- Sirul vid este corect.

- Daca sirul $A$ este corect, atunci si sirul $(A)$ este corect.
- Daca sirurile $A$ si $B$ sunt corecte, atunci si sirul $A$ concatenat cu $B$ este corect.

* $1 ≤ T ≤ 100$
* $1 ≤ N ≤ 10.000$

* $Daca exista mai multe solutii, o vei accepta fericit pe oricare dintre acestea.$

h2. Exemplu

-1
|

In primul test poti imparti cu succes sirul de paranteze in doua subsiruri corecte de paranteze de aceeasi lungime. Excelent.
In al doilea caz nu poti imparti sirul in doua subsiruri corecte. Ai putea face asta daca nu-i oferi toate parantezele, dar nu vrei sa faci asta. Asa esti tu.

In primul test poti partitiona cu succes sirul de paranteze in doua subsiruri corecte de paranteze de aceeasi lungime. Excelent.
In al doilea caz nu poti partitiona sirul in doua subsiruri corecte. Ai putea face asta daca nu-i oferi vecinului toate parantezele, dar nu vrei sa faci asta. Asa esti tu.

== include(page="template/taskfooter" task_id="brackets") ==