Jelefy gra w Wieże Hanoi ze specjalną zasadą.

Wieże Hanoi składają się z trzech słupków: $A$, $B$ oraz $C$, na których można układać krążki. Krążki można przenosić pomiędzy różnymi słupkami, ale należy przestrzegać następujących zasad:

• Naraz można przenieść tylko jeden krążek;
• W każdym ruchu można przenieść wyłącznie krążek leżący na samym wierzchu jednego słupka na sam wierzch innego słupka;
• Na słupkach $B$ i $C$ żadnego krążka nie wolno położyć na mniejszym krążku;
• Na słupku $A$ większe krążki można kłaść na mniejszych krążkach.

Na początku Jelefy losowo układa $n$ krążków o różnych rozmiarach na słupku $A$, pozostawiając słupki $B$ i $C$ puste. Przy powyższych warunkach Jelefy chce wiedzieć, ile ruchów potrzeba, aby przenieść wszystkie krążki ze słupka $A$ na słupek $B$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1\leq T\leq 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego: Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1\leq n\leq 10^5$), oznaczającą liczbę krążków na słupku $A$ w stanie początkowym.

Drugi wiersz zawiera $n$ liczb całkowitych $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), gdzie $p_i$ oznacza średnicę $i$-tego krążka na słupku $A$, licząc od dołu do góry. Gwarantuje się, że $p_1,p_2,\ldots,p_n$ tworzą permutację długości $n$, tzn. każda liczba całkowita od $1$ do $n$ występuje w ciągu dokładnie raz.

Dla wszystkich przypadków testowych gwarantuje się, że $\sum n\leq 2\times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w osobnym wierszu jedną liczbę całkowitą, oznaczającą minimalną wymaganą liczbę ruchów.

Przykład

Wejście 1

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

Wyjście 1

11
5
19

Uwagi

W pierwszym przykładzie jedno z możliwych rozwiązań o minimalnej liczbie ruchów wygląda następująco ($X\rightarrow Y$ oznacza przeniesienie wierzchniego krążka ze słupka $X$ na wierzch słupka $Y$):

• $A\rightarrow C$
• $A\rightarrow B$
• $A\rightarrow C$
• $B\rightarrow C$
• $A\rightarrow B$
• $C\rightarrow A$
• $C\rightarrow A$
• $C\rightarrow B$
• $A\rightarrow B$
• $A\rightarrow B$
• $A\rightarrow B$