Multi-Heads Cup, eller MHC kort sagt, är en världsomspännande programmeringstävling skapad för deltagare med många, många huvuden. År 2023 löste tävlingens huvuddomare, Little Cyan Fish, ett klurigt autentiseringsproblem med hjälp av många typer av parenteser.

Det var första gången Little Cyan Fish såg tävlande med många, många huvuden. Och den här gången tar Little Cyan Fish med sig ett annat parentesproblem till sin bästa vän som har många, många huvuden. Little Cyan Fish har $n$ typer av parenteser i sin hand, och varje typ av parentes är uppdelad i vänsterparenteser och högerparenteser. För enkelhetens skull använder vi $L^i$ för att beteckna den $i$-te typen av vänsterparentes, och $R^i$ för att beteckna den $i$-te typen av högerparentes.

"Hej, glöm inte", tänkte Little Cyan Fish, "jag har ju presenterat vad en balanserad parentesföljd är förut!" För att säkerställa att du förstår begreppet balanserad parentesföljd har Little Cyan Fish förberett följande formella definition av en balanserad parentesföljd:

• $\varepsilon$ (en tom sträng) är en balanserad parentesföljd.
• Om $A$ är en balanserad parentesföljd är $(A)$ också en balanserad parentesföljd.
• Om $A$ och $B$ är balanserade parentesföljder är $AB$ också en balanserad parentesföljd.

Till exempel är "()", "()()" och "(())" balanserade parentesföljder, men ")(", "(" och "))" är det inte.

Nu ger Little Cyan Fish dig en parentesföljd $S$ av längd $n$, som innehåller $n$ typer av parenteser. Tyvärr har Little Cyan Fish glömt vilka typer av parenteser som står på vissa positioner, och har även glömt riktningarna på parenteserna på dessa positioner. Minnet av dessa positioner har blivit suddigt och representeras med ? av Little Cyan Fish.

Little Cyan Fish är mycket nyfiken på hur många par $(l, r)$, för alla $1 \le l \le r \le n$, som motsvarar delsträngar $S[l \dots r]$ sådana att det finns ett sätt att fylla i ? med någon typ av parentes i någon riktning, så att vi för varje $1 \le i \le n$ har:

• Om man extraherar alla parenteser av typ $i$ (dvs. alla $L^i$ och $R^i$), är den resulterande parentesföljden (som endast innehåller den $i$-te typen av parentes) en balanserad parentesföljd.

Om vi till exempel använder "()" för att beteckna den första typen av parentes och "[]" för att beteckna den andra typen av parentes, uppfyller parentessträngen ([?) villkoret ovan eftersom vi kan ersätta ? med ]. (?)] uppfyller också villkoret ovan eftersom vi kan ersätta ? med [.

Little Cyan Fish vill att du beräknar antalet giltiga par $(l, r)$.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden i indata ett heltal $n$ ($1 \le n \le 2 \times 10^5$), som anger längden på parentessträngen.

Nästa rad innehåller $n$ heltal $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Dessa $n$ heltal beskriver informationen om parentessträngen, där:

• Om $x_i > 0$, representerar den $i$-te positionen den $x_i$-te typen av vänsterparentes (dvs. $L^{x_i}$).
• Om $x_i < 0$, representerar den $i$-te positionen den $-x_i$-te typen av högerparentes (dvs. $R^{-x_i}$).
• Om $x_i = 0$, betyder det att Little Cyan Fish har glömt informationen på denna position (dvs. ?).

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett heltal, vilket anger svaret.

Exempel

Indata 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