Aby uczcić fakt, że żadna drużyna nie rozwiązała zadania „Queue Editor” podczas półfinałów 3. edycji Universal Cup, Little Cyan Fish wymyślił nowe zadanie z kolejką oraz... tym razem ze stosem! Ma on $n$ kul ponumerowanych od $1$ do $n$. Kule są początkowo ustawione w kolejce, a ponadto ma on pusty stos. Dopóki kolejka nie jest pusta, wykonuje on następujące kroki:

1. Usuń kulę z początku kolejki. Niech $x$ oznacza jej numer.
2. Dopóki stos nie jest pusty, a numer kuli na jego wierzchu jest większy niż $x$, usuwaj kulę z wierzchu stosu i dołączaj ją na koniec kolejki. Kule są dołączane w kolejności, w jakiej są usuwane.
3. Połóż kulę o numerze $x$ na wierzchu stosu.

Można wykazać, że po skończonej liczbie kroków kolejka stanie się pusta. Wyznacz łączną liczbę razy, kiedy Little Cyan Fish kładzie kulę na stosie, zanim to nastąpi.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^5$), oznaczającą liczbę kul. Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), oznaczających numery kul w początkowej kolejce od początku do końca. Gwarantowane jest, że $a_1, a_2, \ldots, a_n$ tworzą permutację liczb $1, 2, \ldots, n$.

Gwarantowane jest, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w osobnym wierszu jedną liczbę całkowitą, oznaczającą łączną liczbę położeń kuli na stosie.

Przykład

Wejście 1

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

Wyjście 1

1
3
5
4

Wejście 2

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

Wyjście 2

6
15

Uwagi

W pierwszym przykładzie ciągi numerów kładzionych na stosie to odpowiednio $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ oraz $(3, 1, 2, 3)$ w czterech przypadkach testowych. Rysunek w treści zadania ilustruje trzeci przypadek testowy z pierwszego przykładu.

W pierwszym przypadku testowym drugiego przykładu ciąg kładzionych numerów to $(2, 3, 1, 3, 2, 3)$, więc odpowiedzią jest $6$. W drugim przypadku testowym drugiego przykładu ciąg to $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, więc odpowiedzią jest $15$.