For å feire at ingen lag løste oppgaven "Queue Editor" i semifinalen i The 3rd Universal Cup, har Little Cyan Fish kommet opp med en ny oppgave som involverer en kø og... denne gangen, en stakk! Han har $n$ baller merket fra $1$ til $n$. Ballene er opprinnelig plassert i en kø, og han har også en tom stakk. Så lenge køen ikke er tom, utfører han følgende steg:

1. Fjern ballen fremst i køen. La $x$ være merket dens.
2. Så lenge stakken ikke er tom og merket på den øverste ballen er større enn $x$, fjern den øverste ballen fra stakken og legg den til bakerst i køen. Ballene legges til i den rekkefølgen de fjernes.
3. Legg ballen merket $x$ øverst på stakken.

Det kan vises at køen blir tom etter et endelig antall steg. Finn det totale antallet ganger Little Cyan Fish legger en ball på stakken før dette skjer.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et enkelt heltall $T$ ($1 \le T$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et enkelt heltall $n$ ($1 \le n \le 5 \times 10^5$), som angir antallet baller. Den andre linjen inneholder $n$ heltall $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), som angir merkene på ballene i den opprinnelige køen fra fremst til bakerst. Det er garantert at $a_1, a_2, \ldots, a_n$ danner en permutasjon av $1, 2, \ldots, n$.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $5 \times 10^5$.

Utdata

For hvert testtilfelle, skriv ut en enkelt linje som inneholder et enkelt heltall, som angir det totale antallet ganger en ball legges på stakken.

Eksempler

Inndata 1

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

Utdata 1

1
3
5
4

Inndata 2

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

Utdata 2

6
15

Merk

I det første eksempelet er følgene av merker som legges på stakken henholdsvis $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ og $(3, 1, 2, 3)$ i de fire testtilfellene. Figuren i oppgaveteksten illustrerer det tredje testtilfellet i det første eksempelet.

I det første testtilfellet i det andre eksempelet er følgen av merker som legges på stakken $(2, 3, 1, 3, 2, 3)$, så svaret er $6$. I det andre testtilfellet i det andre eksempelet er følgen $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, så svaret er $15$.