Multi-Heads Cup, eller MHC kort fortalt, er en verdensomspennende programmeringskonkurranse laget for deltakere med mange, mange hoder. I 2023 løste hoveddommeren for dette arrangementet, Little Cyan Fish, et vrient autentiseringsproblem ved hjelp av mange typer parenteser.

Det var første gang Little Cyan Fish så deltakere med mange, mange hoder. Og denne gangen tar Little Cyan Fish med seg et nytt parentesproblem til sin beste venn som har mange, mange hoder. Little Cyan Fish har $n$ typer parenteser i hånden, og hver type parentes er delt inn i venstreparenteser og høyreparenteser. For enkelhets skyld bruker vi $L^i$ for å betegne den $i$-te typen venstreparentes, og $R^i$ for å betegne den $i$-te typen høyreparentes.

«Hei, ikke glem det,» tenkte Little Cyan Fish, «jeg har jo introdusert for deg hva en balansert parentesfølge er før!» For å sikre at du forstår konseptet med en balansert parentesfølge, har Little Cyan Fish forberedt følgende formelle definisjon av en balansert parentesfølge:

• $\varepsilon$ (en tom streng) er en balansert parentesfølge.
• Hvis $A$ er en balansert parentesfølge, er $(A)$ også en balansert parentesfølge.
• Hvis $A$ og $B$ er balanserte parentesfølger, så er $AB$ også en balansert parentesfølge.

For eksempel er «()», «()()» og «(())» balanserte parentesfølger, men «)(», «(» og «))» er det ikke.

Nå gir Little Cyan Fish deg en parentesfølge $S$ med lengde $n$, som inneholder $n$ typer parenteser. Dessverre har Little Cyan Fish glemt typene parenteser på noen posisjoner, og har også glemt retningene til parentesene på disse posisjonene. Minnet om disse posisjonene har blitt uklart og er representert med ? av Little Cyan Fish.

Little Cyan Fish er veldig nysgjerrig på hvor mange par $(l, r)$, for alle $1 \le l \le r \le n$, som tilsvarer delstrenger $S[l \dots r]$ slik at det finnes en måte å fylle ? med en eller annen type parentes i en eller annen retning, slik at vi for hver $1 \le i \le n$ har:

• Trekk ut alle parenteser av type $i$ (dvs. alle $L^i$ og $R^i$); den resulterende parentesfølgen (som kun inneholder den $i$-te typen parentes) er en balansert parentesfølge.

For eksempel, hvis vi bruker «()» for å betegne den første typen parentes og «[]» for å betegne den andre typen parentes, tilfredsstiller parentesstrengen ([?) betingelsen ovenfor, fordi vi kan erstatte ? med ]. (?)] tilfredsstiller også betingelsen ovenfor, fordi vi kan erstatte ? med [.

Little Cyan Fish vil at du skal beregne antallet av alle gyldige par $(l, r)$.

Inndata

Det er flere testtilfeller. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen av inndataene et heltall $n$ ($1 \le n \le 2 \times 10^5$), som angir lengden på parentesstrengen.

Den neste linjen inneholder $n$ heltall $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Disse $n$ heltallene beskriver informasjonen om parentesstrengen, der:

• Hvis $x_i > 0$, representerer den $i$-te posisjonen den $x_i$-te typen venstreparentes (dvs. $L^{x_i}$).
• Hvis $x_i < 0$, representerer den $i$-te posisjonen den $-x_i$-te typen høyreparentes (dvs. $R^{-x_i}$).
• Hvis $x_i = 0$, betyr det at Little Cyan Fish har glemt informasjonen på denne posisjonen (dvs. ?).

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder ett heltall, som angir svaret.

Eksempel

Inndata 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

Utdata 1

1
3
3
14