La Multi-Heads Cup, o MHC in breve, è una gara mondiale di programmazione creata per i partecipanti con tante, tante teste. Nel 2023, il giudice capo di questo evento, Little Cyan Fish, ha risolto un complicato problema di autenticazione utilizzando molti tipi di parentesi.

Quella è stata la prima volta che Little Cyan Fish ha visto concorrenti con tante, tante teste. E questa volta, Little Cyan Fish porta un altro problema sulle parentesi al suo migliore amico che ha tante, tante teste. Little Cyan Fish ha in mano $n$ tipi di parentesi, e ogni tipo di parentesi è diviso in parentesi aperte e parentesi chiuse. Per comodità, usiamo $L^i$ per indicare l'$i$-esimo tipo di parentesi aperta e $R^i$ per indicare l'$i$-esimo tipo di parentesi chiusa.

«Ehi, non dimenticare», pensò Little Cyan Fish, «ti ho già spiegato in precedenza cos'è una sequenza di parentesi bilanciata!». Per assicurarsi che tu comprenda il concetto di sequenza di parentesi bilanciata, Little Cyan Fish ha preparato la seguente definizione formale di sequenza di parentesi bilanciata:

• $\varepsilon$ (una stringa vuota) è una sequenza di parentesi bilanciata.
• Se $A$ è una sequenza di parentesi bilanciata, anche $(A)$ è una sequenza di parentesi bilanciata.
• Se $A$ e $B$ sono sequenze di parentesi bilanciate, allora anche $AB$ è una sequenza di parentesi bilanciata.

Ad esempio, «()», «()()» e «(())» sono sequenze di parentesi bilanciate, ma «)(», «(» e «))» non lo sono.

Ora, Little Cyan Fish ti dà una sequenza di parentesi $S$ di lunghezza $n$, contenente $n$ tipi di parentesi. Sfortunatamente, Little Cyan Fish ha dimenticato i tipi di parentesi in alcune posizioni, e ha anche dimenticato le direzioni delle parentesi in queste posizioni. Il ricordo di queste posizioni è diventato sfocato ed è rappresentato con ? da Little Cyan Fish.

Little Cyan Fish è molto curioso di sapere, per tutti gli $1 \le l \le r \le n$, quante coppie $(l, r)$ corrispondono a sottostringhe $S[l \dots r]$ tali che esista un modo di riempire i ? con un qualche tipo di parentesi in una qualche direzione, in modo che per ogni $1 \le i \le n$ si abbia:

• Estraendo tutte le parentesi di tipo $i$ (cioè tutte le $L^i$ e $R^i$), la sequenza di parentesi risultante (contenente solo l'$i$-esimo tipo di parentesi) è una sequenza di parentesi bilanciata.

Ad esempio, se usiamo «()» per indicare il primo tipo di parentesi e «[]» per indicare il secondo tipo di parentesi, la stringa di parentesi ([?) soddisfa la condizione precedente, perché possiamo sostituire ? con ]. Anche (?)] soddisfa la condizione precedente, perché possiamo sostituire ? con [.

Little Cyan Fish vuole che tu calcoli il numero di tutte le coppie valide $(l, r)$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga dell'input contiene un intero $n$ ($1 \le n \le 2 \times 10^5$), che indica la lunghezza della stringa di parentesi.

La riga successiva contiene $n$ interi $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). Questi $n$ interi descrivono le informazioni della stringa di parentesi, dove:

• Se $x_i > 0$, allora l'$i$-esima posizione rappresenta l'$x_i$-esimo tipo di parentesi aperta (cioè $L^{x_i}$).
• Se $x_i < 0$, allora l'$i$-esima posizione rappresenta il $-x_i$-esimo tipo di parentesi chiusa (cioè $R^{-x_i}$).
• Se $x_i = 0$, significa che Little Cyan Fish ha dimenticato l'informazione in questa posizione (cioè ?).

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \times 10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente un intero, che indica la risposta.

Esempio

Input 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

Output 1

1
3
3
14