Para celebrar el hecho de que ningún equipo resolvió el problema «Queue Editor» en las semifinales de la 3.ª Universal Cup, a Little Cyan Fish se le ha ocurrido un nuevo problema que involucra una cola y... ¡esta vez, una pila! Tiene $n$ bolas etiquetadas del $1$ al $n$. Las bolas están dispuestas inicialmente en una cola, y también tiene una pila vacía. Mientras la cola no esté vacía, realiza los siguientes pasos:

1. Retirar la bola que está al frente de la cola. Sea $x$ su etiqueta.
2. Mientras la pila no esté vacía y la etiqueta de la bola en su cima sea mayor que $x$, retirar la bola de la cima de la pila y añadirla al final de la cola. Las bolas se añaden en el orden en que son retiradas.
3. Apilar la bola etiquetada con $x$ en la cima de la pila.

Se puede demostrar que la cola queda vacía tras un número finito de pasos. Halla el número total de veces que Little Cyan Fish apila una bola en la pila antes de que esto ocurra.

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 contiene un único entero $n$ ($1 \le n \le 5 \times 10^5$), que indica el número de bolas. La segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), que indican las etiquetas de las bolas en la cola inicial desde el frente hasta el final. Se garantiza que $a_1, a_2, \ldots, a_n$ forman una permutación de $1, 2, \ldots, n$.

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

Salida

Para cada caso de prueba, imprime una única línea con un único entero, que indique el número total de veces que una bola es apilada en la pila.

Ejemplos

Entrada 1

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

Salida 1

1
3
5
4

Entrada 2

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

Salida 2

6
15

Nota

En el primer ejemplo, las secuencias de etiquetas apiladas en la pila son $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ y $(3, 1, 2, 3)$ en los cuatro casos de prueba, respectivamente. La figura del enunciado ilustra el tercer caso de prueba del primer ejemplo.

En el primer caso de prueba del segundo ejemplo, la secuencia de etiquetas apiladas es $(2, 3, 1, 3, 2, 3)$, por lo que la respuesta es $6$. En el segundo caso de prueba del segundo ejemplo, la secuencia es $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, por lo que la respuesta es $15$.