Der Multi-Heads Cup, kurz MHC, ist ein weltweiter Programmierwettbewerb für Teilnehmer mit vielen, vielen Köpfen. Im Jahr 2023 löste der Hauptschiedsrichter dieser Veranstaltung, Little Cyan Fish, ein kniffliges Authentifizierungsproblem mithilfe vieler Arten von Klammern.

Das war das erste Mal, dass Little Cyan Fish Teilnehmer mit vielen, vielen Köpfen sah. Und dieses Mal bringt Little Cyan Fish seinem besten Freund, der ebenfalls viele, viele Köpfe hat, ein weiteres Klammerproblem mit. Little Cyan Fish hat $n$ Arten von Klammern in der Hand, und jede Klammerart ist in öffnende und schließende Klammern unterteilt. Der Einfachheit halber verwenden wir $L^i$ für die $i$-te Art von öffnender Klammer und $R^i$ für die $i$-te Art von schließender Klammer.

„Hey, vergiss nicht“, dachte Little Cyan Fish, „ich habe dir schon einmal erklärt, was eine ausgeglichene Klammerfolge ist!“ Um sicherzustellen, dass du das Konzept einer ausgeglichenen Klammerfolge verstehst, hat Little Cyan Fish die folgende formale Definition einer ausgeglichenen Klammerfolge vorbereitet:

• $\varepsilon$ (eine leere Zeichenkette) ist eine ausgeglichene Klammerfolge.
• Wenn $A$ eine ausgeglichene Klammerfolge ist, ist $(A)$ ebenfalls eine ausgeglichene Klammerfolge.
• Wenn $A$ und $B$ ausgeglichene Klammerfolgen sind, dann ist $AB$ ebenfalls eine ausgeglichene Klammerfolge.

Beispielsweise sind „()“, „()()“ und „(())“ ausgeglichene Klammerfolgen, aber „)(“, „(“ und „))“ nicht.

Nun gibt dir Little Cyan Fish eine Klammerfolge $S$ der Länge $n$, die $n$ Arten von Klammern enthält. Leider hat Little Cyan Fish an einigen Positionen die Klammerart und auch die Klammerrichtung vergessen. Die Erinnerung an diese Positionen ist verschwommen und wird von Little Cyan Fish durch ? dargestellt.

Little Cyan Fish ist sehr neugierig, wie viele Paare $(l, r)$ für alle $1 \le l \le r \le n$ Teilzeichenketten $S[l \dots r]$ entsprechen, sodass es eine Möglichkeit gibt, ? mit einer bestimmten Klammerart in einer bestimmten Richtung zu füllen, sodass für jedes $1 \le i \le n$ gilt:

• Extrahiert man alle Klammern vom Typ $i$ (d. h. alle $L^i$ und $R^i$), so ist die resultierende Klammerfolge (die nur die $i$-te Klammerart enthält) eine ausgeglichene Klammerfolge.

Wenn wir beispielsweise „()“ für die erste Klammerart und „[]“ für die zweite Klammerart verwenden, erfüllt die Klammerzeichenkette ([?) die obige Bedingung, da wir ? durch ] ersetzen können. (?)] erfüllt die obige Bedingung ebenfalls, da wir ? durch [ ersetzen können.

Little Cyan Fish möchte, dass du die Anzahl aller gültigen Paare $(l, r)$ berechnest.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile der Eingabe eine ganze Zahl $n$ ($1 \le n \le 2 \times 10^5$), die die Länge der Klammerzeichenkette angibt.

Die nächste Zeile enthält $n$ ganze Zahlen $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Diese $n$ ganzen Zahlen beschreiben die Informationen der Klammerzeichenkette, wobei:

• Wenn $x_i > 0$, stellt die $i$-te Position die $x_i$-te Art von öffnender Klammer dar (d. h. $L^{x_i}$).
• Wenn $x_i < 0$, stellt die $i$-te Position die $-x_i$-te Art von schließender Klammer dar (d. h. $R^{-x_i}$).
• Wenn $x_i = 0$, bedeutet dies, dass Little Cyan Fish die Information an dieser Position vergessen hat (d. h. ?).

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die die Antwort angibt.

Beispiel

Eingabe 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

Ausgabe 1

1
3
3
14