Multi-Heads Cup, eða MHC í stuttu máli, er alþjóðleg forritunarkeppni sem haldin er fyrir keppendur með mörg, mörg höfuð. Árið 2023 leysti yfirdómari þessa viðburðar, Little Cyan Fish, snúið auðkenningarvandamál með því að nota margar tegundir af svigum.

Það var í fyrsta skipti sem Little Cyan Fish sá keppendur með mörg, mörg höfuð. Og í þetta sinn færir Little Cyan Fish besta vini sínum, sem er með mörg, mörg höfuð, annað svigaverkefni. Little Cyan Fish er með $n$ tegundir af svigum í hendinni og hver tegund sviga skiptist í vinstri sviga og hægri sviga. Til hægðarauka notum við $L^i$ til að tákna $i$-tu tegund vinstri sviga og $R^i$ til að tákna $i$-tu tegund hægri sviga.

„Heyrðu, ekki gleyma,“ hugsaði Little Cyan Fish, „ég hef áður kynnt fyrir þér hvað jafnvægissvigastrengur er!“ Til að tryggja að þú skiljir hugtakið jafnvægissvigastrengur útbjó Little Cyan Fish eftirfarandi formlega skilgreiningu á jafnvægissvigastreng:

• $\varepsilon$ (tómur strengur) er jafnvægissvigastrengur.
• Ef $A$ er jafnvægissvigastrengur, þá er $(A)$ líka jafnvægissvigastrengur.
• Ef $A$ og $B$ eru jafnvægissvigastrengir, þá er $AB$ líka jafnvægissvigastrengur.

Til dæmis eru „()“, „()()“ og „(())“ jafnvægissvigastrengir, en „)(“, „(“ og „))“ eru það ekki.

Nú gefur Little Cyan Fish þér svigastreng $S$ af lengd $n$, sem inniheldur $n$ tegundir af svigum. Því miður gleymdi Little Cyan Fish tegundum sviganna á sumum stöðum, og gleymdi einnig áttum sviganna á þessum stöðum. Minningin um þessa staði hefur orðið óskýr og er táknuð með ? hjá Little Cyan Fish.

Little Cyan Fish er mjög forvitinn um hversu mörg pör $(l, r)$, fyrir öll $1 \le l \le r \le n$, samsvara hlutstrengjum $S[l \dots r]$ þannig að til sé leið til að fylla í ? með einhverri tegund sviga í einhverja átt, þannig að fyrir hvert $1 \le i \le n$ gildi:

• Ef allir svigar af tegund $i$ (þ.e. allir $L^i$ og $R^i$) eru dregnir út, þá er svigastrengurinn sem fæst (sem inniheldur aðeins $i$-tu tegund sviga) jafnvægissvigastrengur.

Til dæmis, ef við notum „()“ til að tákna fyrstu tegund sviga og „[]“ til að tákna aðra tegund sviga, þá uppfyllir svigastrengurinn ([?) skilyrðið hér að ofan, vegna þess að við getum skipt ? út fyrir ]. (?)] uppfyllir einnig skilyrðið hér að ofan, vegna þess að við getum skipt ? út fyrir [.

Little Cyan Fish vill að þú reiknir fjölda allra gildra para $(l, r)$.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan í inntakinu heiltölu $n$ ($1 \le n \le 2 \times 10^5$), sem gefur til kynna lengd svigastrengsins.

Næsta lína inniheldur $n$ heiltölur $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Þessar $n$ heiltölur lýsa upplýsingum svigastrengsins, þar sem:

• Ef $x_i > 0$, þá táknar $i$-ti staðurinn $x_i$-tu tegund vinstri sviga (þ.e. $L^{x_i}$).
• Ef $x_i < 0$, þá táknar $i$-ti staðurinn $-x_i$-tu tegund hægri sviga (þ.e. $R^{-x_i}$).
• Ef $x_i = 0$, þá þýðir það að Little Cyan Fish gleymdi upplýsingunum á þessum stað (þ.e. ?).

Tryggt er að summa $n$ yfir öll prófunartilvik fer ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna svarið.

Dæmi

Inntak 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

Úttak 1

1
3
3
14