Um zu feiern, dass beim Halbfinale des 3. Universal Cup kein einziges Team die Aufgabe „Queue Editor“ gelöst hat, hat sich Little Cyan Fish eine neue Aufgabe ausgedacht, bei der es um eine Warteschlange (Queue) und... diesmal auch um einen Stapel (Stack) geht! Er hat $n$ Bälle, die von $1$ bis $n$ beschriftet sind. Die Bälle sind anfangs in einer Warteschlange angeordnet, und außerdem hat er einen leeren Stapel. Solange die Warteschlange nicht leer ist, führt er die folgenden Schritte aus:

1. Entferne den vordersten Ball aus der Warteschlange. Sei $x$ seine Beschriftung.
2. Solange der Stapel nicht leer ist und die Beschriftung seines obersten Balls größer als $x$ ist, entferne den obersten Ball vom Stapel und füge ihn am Ende der Warteschlange an. Die Bälle werden in der Reihenfolge angefügt, in der sie entfernt werden.
3. Lege den mit $x$ beschrifteten Ball oben auf den Stapel.

Es lässt sich zeigen, dass die Warteschlange nach endlich vielen Schritten leer wird. Bestimme die Gesamtzahl der Male, die Little Cyan Fish einen Ball auf den Stapel legt, bevor dies geschieht.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $n$ ($1 \le n \le 5 \times 10^5$), die die Anzahl der Bälle angibt. Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), die die Beschriftungen der Bälle in der anfänglichen Warteschlange von vorne nach hinten angeben. Es wird garantiert, dass $a_1, a_2, \ldots, a_n$ eine Permutation von $1, 2, \ldots, n$ bilden.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $5 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer einzelnen ganzen Zahl aus, die angibt, wie oft insgesamt ein Ball auf den Stapel gelegt wird.

Beispiele

Eingabe 1

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

Ausgabe 1

1
3
5
4

Eingabe 2

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

Ausgabe 2

6
15

Hinweis

Im ersten Beispiel lauten die Folgen der auf den Stapel gelegten Beschriftungen in den vier Testfällen $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ bzw. $(3, 1, 2, 3)$. Die Abbildung in der Aufgabenstellung veranschaulicht den dritten Testfall im ersten Beispiel.

Im ersten Testfall des zweiten Beispiels lautet die Folge der auf den Stapel gelegten Beschriftungen $(2, 3, 1, 3, 2, 3)$, sodass die Antwort $6$ ist. Im zweiten Testfall des zweiten Beispiels lautet die Folge $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, sodass die Antwort $15$ ist.