För att fira att inget lag löste problemet "Queue Editor" i semifinalen av The 3rd Universal Cup har Little Cyan Fish kommit på ett nytt problem som involverar en kö och... den här gången, en stack! Han har $n$ bollar märkta från $1$ till $n$. Bollarna är från början placerade i en kö, och han har även en tom stack. Så länge kön inte är tom utför han följande steg:

1. Ta bort bollen längst fram i kön. Låt $x$ vara dess etikett.
2. Så länge stacken inte är tom och etiketten på dess översta boll är större än $x$, ta bort den översta bollen från stacken och lägg till den längst bak i kön. Bollarna läggs till i den ordning de tas bort.
3. Lägg bollen med etiketten $x$ överst på stacken.

Det går att visa att kön blir tom efter ett ändligt antal steg. Bestäm det totala antalet gånger Little Cyan Fish lägger en boll på stacken innan detta sker.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $n$ ($1 \le n \le 5 \times 10^5$), som anger antalet bollar. Den andra raden innehåller $n$ heltal $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), som anger etiketterna på bollarna i den ursprungliga kön från början till slut. Det garanteras att $a_1, a_2, \ldots, a_n$ utgör en permutation av $1, 2, \ldots, n$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $5 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett enda heltal, vilket anger det totala antalet gånger en boll läggs på stacken.

Exempel

Indata 1

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

Utdata 1

1
3
5
4

Indata 2

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

Utdata 2

6
15

Kommentar

I det första exemplet är följderna av etiketter som läggs på stacken $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ respektive $(3, 1, 2, 3)$ i de fyra testfallen. Figuren i problembeskrivningen illustrerar det tredje testfallet i det första exemplet.

I det första testfallet i det andra exemplet är följden av etiketter som läggs på stacken $(2, 3, 1, 3, 2, 3)$, så svaret är $6$. I det andra testfallet i det andra exemplet är följden $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, så svaret är $15$.