La Multi-Heads Cup, o MHC para abreviar, es un concurso mundial de programación creado para participantes con muchas, muchas cabezas. En 2023, el juez principal de este evento, Little Cyan Fish, resolvió un complicado problema de autenticación utilizando muchos tipos de paréntesis.

Esa fue la primera vez que Little Cyan Fish vio concursantes con muchas, muchas cabezas. Y esta vez, Little Cyan Fish le trae otro problema de paréntesis a su mejor amigo, que tiene muchas, muchas cabezas. Little Cyan Fish tiene $n$ tipos de paréntesis en su mano, y cada tipo de paréntesis se divide en paréntesis izquierdos y paréntesis derechos. Por conveniencia, usamos $L^i$ para denotar el $i$-ésimo tipo de paréntesis izquierdo, y $R^i$ para denotar el $i$-ésimo tipo de paréntesis derecho.

«Oye, no lo olvides», pensó Little Cyan Fish, «¡ya te he presentado antes qué es una secuencia de paréntesis balanceada!». Para asegurarse de que comprendes el concepto de secuencia de paréntesis balanceada, Little Cyan Fish preparó la siguiente definición formal de una secuencia de paréntesis balanceada:

• $\varepsilon$ (una cadena vacía) es una secuencia de paréntesis balanceada.
• Si $A$ es una secuencia de paréntesis balanceada, $(A)$ también es una secuencia de paréntesis balanceada.
• Si $A$ y $B$ son secuencias de paréntesis balanceadas, entonces $AB$ también es una secuencia de paréntesis balanceada.

Por ejemplo, «()», «()()» y «(())» son secuencias de paréntesis balanceadas, pero «)(», «(» y «))» no lo son.

Ahora, Little Cyan Fish te da una secuencia de paréntesis $S$ de longitud $n$, que contiene $n$ tipos de paréntesis. Desafortunadamente, Little Cyan Fish olvidó los tipos de paréntesis en algunas posiciones y también olvidó las direcciones de los paréntesis en esas posiciones. El recuerdo de estas posiciones se ha vuelto borroso y Little Cyan Fish lo representa mediante ?.

Little Cyan Fish tiene mucha curiosidad por saber, para todo $1 \le l \le r \le n$, cuántos pares $(l, r)$ corresponden a subcadenas $S[l \dots r]$ tales que existe una forma de rellenar los ? con algún tipo de paréntesis en alguna dirección, de modo que para cada $1 \le i \le n$ se cumpla:

• Al extraer todos los paréntesis de tipo $i$ (es decir, todos los $L^i$ y $R^i$), la secuencia de paréntesis resultante (que contiene únicamente el $i$-ésimo tipo de paréntesis) es una secuencia de paréntesis balanceada.

Por ejemplo, si usamos «()» para denotar el primer tipo de paréntesis y «[]» para denotar el segundo tipo de paréntesis, la cadena de paréntesis ([?) satisface la condición anterior, porque podemos reemplazar ? con ]. (?)] también satisface la condición anterior, porque podemos reemplazar ? con [.

Little Cyan Fish quiere que calcules el número de todos los pares válidos $(l, r)$.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea de la entrada contiene un entero $n$ ($1 \le n \le 2 \times 10^5$), que indica la longitud de la cadena de paréntesis.

La siguiente línea contiene $n$ enteros $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Estos $n$ enteros describen la información de la cadena de paréntesis, donde:

• Si $x_i > 0$, entonces la $i$-ésima posición representa el $x_i$-ésimo tipo de paréntesis izquierdo (es decir, $L^{x_i}$).
• Si $x_i < 0$, entonces la $i$-ésima posición representa el $-x_i$-ésimo tipo de paréntesis derecho (es decir, $R^{-x_i}$).
• Si $x_i = 0$, significa que Little Cyan Fish olvidó la información en esta posición (es decir, ?).

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un entero, indicando la respuesta.

Ejemplo

Entrada 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

Salida 1

1
3
3
14