Multi-Heads Cup, lyhyesti MHC, on maailmanlaajuinen ohjelmointikilpailu, joka on tarkoitettu osallistujille, joilla on monta, monta päätä. Vuonna 2023 tämän tapahtuman päätuomari Little Cyan Fish ratkaisi hankalan tunnistautumisongelman käyttämällä monenlaisia sulkeita.

Se oli ensimmäinen kerta, kun Little Cyan Fish näki kilpailijoita, joilla on monta, monta päätä. Ja tällä kertaa Little Cyan Fish tuo toisen sulkeisiin liittyvän tehtävän parhaalle ystävälleen, jolla on monta, monta päätä. Little Cyan Fishillä on kädessään $n$ eri tyyppistä suljetta, ja jokainen suljetyyppi jakautuu vasempiin sulkeisiin ja oikeisiin sulkeisiin. Mukavuuden vuoksi merkitsemme symbolilla $L^i$ $i$:nnen tyypin vasenta suljetta ja symbolilla $R^i$ $i$:nnen tyypin oikeaa suljetta.

"Hei, älä unohda", Little Cyan Fish ajatteli, "olenhan jo aiemmin esitellyt sinulle, mikä tasapainoinen sulkujono on!" Varmistaakseen, että ymmärrät tasapainoisen sulkujonon käsitteen, Little Cyan Fish laati seuraavan tasapainoisen sulkujonon täsmällisen määritelmän:

• $\varepsilon$ (tyhjä merkkijono) on tasapainoinen sulkujono.
• Jos $A$ on tasapainoinen sulkujono, niin myös $(A)$ on tasapainoinen sulkujono.
• Jos $A$ ja $B$ ovat tasapainoisia sulkujonoja, niin myös $AB$ on tasapainoinen sulkujono.

Esimerkiksi "()", "()()" ja "(())" ovat tasapainoisia sulkujonoja, mutta ")(", "(" ja "))" eivät ole.

Nyt Little Cyan Fish antaa sinulle pituutta $n$ olevan sulkujonon $S$, joka sisältää $n$ eri tyyppistä suljetta. Valitettavasti Little Cyan Fish on unohtanut sulkeiden tyypit joissakin kohdissa ja myös sulkeiden suunnat näissä kohdissa. Muistikuva näistä kohdista on hämärtynyt, ja Little Cyan Fish merkitsee niitä merkillä ?.

Little Cyan Fish on hyvin utelias tietämään, kuinka moni pari $(l, r)$ kaikilla $1 \le l \le r \le n$ vastaa sellaista osamerkkijonoa $S[l \dots r]$, että merkit ? on mahdollista täyttää jonkin tyyppisellä sulkeella jossakin suunnassa siten, että jokaisella $1 \le i \le n$ pätee:

• Kun poimitaan kaikki tyypin $i$ sulkeet (eli kaikki $L^i$ ja $R^i$), saatu sulkujono (joka sisältää vain $i$:nnen tyypin sulkeita) on tasapainoinen sulkujono.

Jos esimerkiksi merkitsemme ensimmäisen tyypin sulkeita merkkijonolla "()" ja toisen tyypin sulkeita merkkijonolla "[]", niin sulkumerkkijono ([?) täyttää yllä olevan ehdon, koska voimme korvata merkin ? merkillä ]. Myös (?)] täyttää yllä olevan ehdon, koska voimme korvata merkin ? merkillä [.

Little Cyan Fish haluaa sinun laskevan kaikkien kelvollisten parien $(l, r)$ lukumäärän.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisessa testitapauksessa syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \times 10^5$), joka ilmoittaa sulkumerkkijonon pituuden.

Seuraava rivi sisältää $n$ kokonaislukua $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Nämä $n$ kokonaislukua kuvaavat sulkumerkkijonon tiedot, missä:

• Jos $x_i > 0$, niin $i$:s kohta esittää $x_i$:nnen tyypin vasenta suljetta (eli $L^{x_i}$).
• Jos $x_i < 0$, niin $i$:s kohta esittää $-x_i$:nnen tyypin oikeaa suljetta (eli $R^{-x_i}$).
• Jos $x_i = 0$, se tarkoittaa, että Little Cyan Fish on unohtanut tämän kohdan tiedot (eli ?).

On taattua, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun — tehtävän vastauksen.

Esimerkki

Syöte 1

4
4
1 2 -1 -2
4
1 0 -2 0
6
1 2 3 -3 -2 -1
8
1 0 0 3 0 0 0 -2

Tuloste 1

1
3
3
14