Per festeggiare il fatto che nessuna squadra abbia risolto il problema «Queue Editor» alle semifinali della 3ª Universal Cup, Little Cyan Fish ha ideato un nuovo problema che coinvolge una coda e... questa volta, una pila! Ha $n$ palline etichettate da $1$ a $n$. Le palline sono inizialmente disposte in una coda, e ha anche una pila vuota. Finché la coda non è vuota, esegue i seguenti passaggi:

1. Rimuovere la pallina in testa alla coda. Sia $x$ la sua etichetta.
2. Finché la pila non è vuota e l'etichetta della pallina in cima ad essa è maggiore di $x$, rimuovere la pallina in cima alla pila e aggiungerla in fondo alla coda. Le palline vengono aggiunte nell'ordine in cui vengono rimosse.
3. Inserire la pallina etichettata con $x$ in cima alla pila.

Si può dimostrare che la coda diventa vuota dopo un numero finito di passaggi. Trova il numero totale di volte in cui Little Cyan Fish inserisce una pallina nella pila prima che ciò accada.

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 ciascun caso di test, la prima riga contiene un singolo intero $n$ ($1 \le n \le 5 \times 10^5$), che indica il numero di palline. La seconda riga contiene $n$ interi $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), che indicano le etichette delle palline nella coda iniziale dalla testa alla fine. È garantito che $a_1, a_2, \ldots, a_n$ formino una permutazione di $1, 2, \ldots, n$.

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

Output

Per ciascun caso di test, stampa una singola riga contenente un singolo intero, che indica il numero totale di volte in cui una pallina viene inserita nella pila.

Esempi

Input 1

4
1
1
3
1 2 3
3
2 1 3
3
3 1 2

Output 1

1
3
5
4

Input 2

2
3
2 3 1
6
1 3 4 6 2 5

Output 2

6
15

Nota

Nel primo esempio, le sequenze di etichette inserite nella pila sono $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ e $(3, 1, 2, 3)$ nei quattro casi di test, rispettivamente. La figura nel testo del problema illustra il terzo caso di test del primo esempio.

Nel primo caso di test del secondo esempio, la sequenza di etichette inserite è $(2, 3, 1, 3, 2, 3)$, quindi la risposta è $6$. Nel secondo caso di test del secondo esempio, la sequenza è $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, quindi la risposta è $15$.