5. Interpunkčné párovanie

Igor a Ignác sú, ako inak, dvojičky. Nepoznajú nudu, keďže odmalička sa vo všetkom predbiehajú. Ten začal prvý rozprávať, tamten prvý napočítal do desať, jeden zahral na klavíri Ódu na radosť, druhý nakreslil slušnú trojbodovú perspektívu, atď. Ešte aj v škole sa im zapáčilo rovnaké dievča. Renáta mala ale oči pre iného a bratia sa tak dlho na seba nehnevali.

“Počuj, Ignác,” začal včera jeden z bratov. “Ukážem ti zátvorkovú šifru, ktorú som dnes vymyslel. Napíšem nejaký zátvorkový reťazec z (, ), [, ], { a }, v ktorom práve jedna zátvorka nemá pár.”

“Krása” odvetil Ignác.

“Čakaj, to ešte nie je všetko. Nemám to úplne domyslené, ale ak je možné chýbajúcu zátvorku do reťazcu doplniť tak, aby bol správne ozátvorkovaný, hodnota správy je \(1\), inak je to \(0\),” objasnil Igor.

“Eh, je pravda, že pomocou \(1\) a \(0\) by sme vedeli po bitoch posielať ľubovoľné správy, ale bolo by to dosť nepraktické. Pravdaže, ak by sme dokázali v jednom reťazci uchovať väčšie číslo, ktorým by sa dala reprezentovať komplexnejšia informácia, dosť by sa používanie tejto šifry zjednodušilo,” navrhuje Ignác.

“Ako by sa to dalo spraviť?”

“Rovnako, ako si to vymyslel, ale trošku zložitejšie. Namiesto toho, či sa chýbajúca zátvorka dá vložiť do reťazca, spočítame, na koľko rôznych pozícií sa dá vložiť, pričom vždy bude možne zátvorku správne vložiť.”

“Výborne! A keďže zátvorky sú párové interpunkčné znamienka, dáme šifre aj taký názov.”

“No dobre.”

I keď chlapci už majú program, ktorý dokáže zakódovať nejakú správu do Interpunkčného párovania, nezvýšil sa im už žiaden čas, aby vytvorili dešifrovací program. Ešteže existujú šikovní KSPáci, ktorí im s tým pomôžu.

Úloha

Na vstupe je reťazec zo zátvoriek (, ), [, ], { a }. Tento reťazec bol najprv správne ozátvorkovaný, no práve jedna zátvorka z neho zmizla. Zistite, na koľko rôznych miest môžeme chýbajúcu zátvorku doplniť tak, aby bolo ozátvorkovanie korektné. Napríklad [{]} je nesprávne ozátvorkovanie. Tak isto aj )[{}]( alebo ({)}. Naopak ({}[]), {[[]]()}{} alebo []{}() sú správne ozátvorkovania.

Formát vstupu

V prvom riadku vstupu je číslo \(1 \leq t \leq 1\,000\) udávajúce počet reťazcov. Nasleduje \(t\) riadkov. V každom riadku sa nachádza reťazec \(n\) znakov zátvoriek (, ), [, ], { a }. Práve jedna zátvorka v reťazci chýba. Platí: \(n = k + 1\) a \(0 \leq k \leq 2\,000\).

Formát výstupu

Vypíšte jedno celé číslo: počet miest v reťazci, kam vieme korektne vložiť chýbajúcu zátvorku.

Príklady

Input:

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

Output:

1
3
6
1