Juhlistaakseen sitä, että yksikään joukkue ei ratkaissut tehtävää "Queue Editor" The 3rd Universal Cupin semifinaalissa, Little Cyan Fish on keksinyt uuden tehtävän, johon liittyy jono ja... tällä kertaa myös pino! Hänellä on $n$ palloa, jotka on numeroitu luvuilla $1$:stä $n$:ään. Pallot on aluksi järjestetty jonoon, ja hänellä on lisäksi tyhjä pino. Niin kauan kuin jono ei ole tyhjä, hän suorittaa seuraavat vaiheet:

1. Poista jonon ensimmäinen pallo. Olkoon sen numero $x$.
2. Niin kauan kuin pino ei ole tyhjä ja sen päällimmäisen pallon numero on suurempi kuin $x$, poista päällimmäinen pallo pinosta ja lisää se jonon perälle. Pallot lisätään jonon perälle siinä järjestyksessä, jossa ne poistetaan pinosta.
3. Aseta pallo, jonka numero on $x$, pinon päälle.

Voidaan osoittaa, että jono tyhjenee äärellisen monta vaihetta suoritettuaan. Selvitä, kuinka monta kertaa yhteensä Little Cyan Fish asettaa pallon pinoon ennen kuin näin tapahtuu.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 5 \times 10^5$), joka ilmoittaa pallojen lukumäärän. Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), jotka ilmoittavat pallojen numerot alkuperäisessä jonossa edestä taakse. On taattu, että $a_1, a_2, \ldots, a_n$ muodostavat lukujen $1, 2, \ldots, n$ permutaation.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $5 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: kuinka monta kertaa yhteensä pallo asetetaan pinoon.

Esimerkit

Syöte 1

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

Tuloste 1

1
3
5
4

Syöte 2

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

Tuloste 2

6
15

Huomautus

Ensimmäisessä esimerkissä pinoon asetettujen pallojen numeroiden jonot ovat $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ ja $(3, 1, 2, 3)$ neljässä testitapauksessa vastaavasti. Tehtävänannon kuva havainnollistaa ensimmäisen esimerkin kolmatta testitapausta.

Toisen esimerkin ensimmäisessä testitapauksessa pinoon asetettujen numeroiden jono on $(2, 3, 1, 3, 2, 3)$, joten vastaus on $6$. Toisen esimerkin toisessa testitapauksessa jono on $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, joten vastaus on $15$.