La Multi-Heads Cup, ou MHC en abrégé, est un concours mondial de programmation conçu pour les participants ayant beaucoup, beaucoup de têtes. En 2023, le juge en chef de cet événement, Little Cyan Fish, a résolu un problème d'authentification délicat en utilisant de nombreux types de parenthèses.

C'était la première fois que Little Cyan Fish voyait des concurrents avec beaucoup, beaucoup de têtes. Et cette fois-ci, Little Cyan Fish apporte un autre problème de parenthèses à son meilleur ami qui a beaucoup, beaucoup de têtes. Little Cyan Fish a $n$ types de parenthèses entre les mains, et chaque type de parenthèse est divisé en parenthèses ouvrantes et parenthèses fermantes. Par commodité, nous utilisons $L^i$ pour désigner le $i$-ème type de parenthèse ouvrante, et $R^i$ pour désigner le $i$-ème type de parenthèse fermante.

« Hé, n'oublie pas, » pensa Little Cyan Fish, « je t'ai déjà présenté ce qu'est une séquence de parenthèses équilibrée auparavant ! » Pour s'assurer que vous comprenez le concept de séquence de parenthèses équilibrée, Little Cyan Fish a préparé la définition formelle suivante d'une séquence de parenthèses équilibrée :

• $\varepsilon$ (une chaîne vide) est une séquence de parenthèses équilibrée.
• Si $A$ est une séquence de parenthèses équilibrée, $(A)$ est aussi une séquence de parenthèses équilibrée.
• Si $A$ et $B$ sont des séquences de parenthèses équilibrées, alors $AB$ est aussi une séquence de parenthèses équilibrée.

Par exemple, « () », « ()() » et « (()) » sont des séquences de parenthèses équilibrées, mais « )( », « ( » et « )) » ne le sont pas.

Maintenant, Little Cyan Fish vous donne une séquence de parenthèses $S$ de longueur $n$, contenant $n$ types de parenthèses. Malheureusement, Little Cyan Fish a oublié les types de parenthèses à certaines positions, et a également oublié les directions des parenthèses à ces positions. Le souvenir de ces positions est devenu flou et est représenté par ? par Little Cyan Fish.

Little Cyan Fish est très curieux de savoir, pour tous $1 \le l \le r \le n$, combien de paires $(l, r)$ correspondent à des sous-chaînes $S[l \dots r]$ telles qu'il existe une façon de remplacer chaque ? par un certain type de parenthèse dans une certaine direction, de sorte que pour chaque $1 \le i \le n$, on ait :

• En extrayant toutes les parenthèses de type $i$ (c'est-à-dire tous les $L^i$ et $R^i$), la séquence de parenthèses résultante (ne contenant que le $i$-ème type de parenthèse) est une séquence de parenthèses équilibrée.

Par exemple, si nous utilisons « () » pour désigner le premier type de parenthèse et « [] » pour désigner le deuxième type de parenthèse, la chaîne de parenthèses ([?) satisfait la condition ci-dessus, car nous pouvons remplacer ? par ]. (?)] satisfait également la condition ci-dessus, car nous pouvons remplacer ? par [.

Little Cyan Fish veut que vous calculiez le nombre de toutes les paires $(l, r)$ valides.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne de l'entrée contient un entier $n$ ($1 \le n \le 2 \times 10^5$), indiquant la longueur de la chaîne de parenthèses.

La ligne suivante contient $n$ entiers $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Ces $n$ entiers décrivent les informations de la chaîne de parenthèses, où :

• Si $x_i > 0$, alors la $i$-ème position représente le $x_i$-ème type de parenthèse ouvrante (c'est-à-dire $L^{x_i}$).
• Si $x_i < 0$, alors la $i$-ème position représente le $-x_i$-ème type de parenthèse fermante (c'est-à-dire $R^{-x_i}$).
• Si $x_i = 0$, cela signifie que Little Cyan Fish a oublié l'information à cette position (c'est-à-dire ?).

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier, indiquant la réponse.

Exemple

Entrée 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

Sortie 1

1
3
3
14