Jelefy spielt die Türme von Hanoi mit einer Sonderregel.

Die Türme von Hanoi bestehen aus drei Stäben $A$, $B$ und $C$, auf denen Scheiben gestapelt werden können. Die Scheiben können zwischen verschiedenen Stäben bewegt werden, müssen dabei jedoch die folgenden Regeln einhalten:

• Es darf jeweils nur eine Scheibe auf einmal bewegt werden;
• Jeder Zug darf nur die oberste Scheibe eines Stabes ganz nach oben auf einen anderen Stab legen;
• Auf den Stäben $B$ und $C$ darf keine Scheibe auf eine kleinere Scheibe gelegt werden;
• Auf Stab $A$ dürfen größere Scheiben auf kleinere Scheiben gelegt werden.

Zu Beginn stapelt Jelefy zufällig $n$ Scheiben unterschiedlicher Größe auf Stab $A$ und lässt die Stäbe $B$ und $C$ leer. Unter den obigen Bedingungen möchte Jelefy wissen, wie viele Züge nötig sind, um alle Scheiben von Stab $A$ nach Stab $B$ zu bewegen.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1\leq T\leq 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall: Die erste Zeile enthält eine ganze Zahl $n$ ($1\leq n\leq 10^5$), die die Anzahl der Scheiben auf Stab $A$ im Anfangszustand angibt.

Die zweite Zeile enthält $n$ ganze Zahlen $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), wobei $p_i$ den Durchmesser der $i$-ten Scheibe auf Stab $A$ von unten nach oben angibt. Es wird garantiert, dass $p_1,p_2,\ldots,p_n$ eine Permutation der Länge $n$ bilden, d. h. jede ganze Zahl von $1$ bis $n$ kommt in der Folge genau einmal vor.

Für alle Testfälle wird garantiert, dass $\sum n\leq 2\times 10^5$ gilt.

Ausgabe

Geben Sie für jeden Testfall in einer eigenen Zeile eine ganze Zahl aus, die die minimale Anzahl erforderlicher Züge angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

11
5
19

Hinweis

Im ersten Beispiel lautet eine mögliche Lösung mit der minimalen Anzahl von Zügen wie folgt ($X\rightarrow Y$ bedeutet, die oberste Scheibe von Stab $X$ ganz nach oben auf Stab $Y$ zu legen):

• $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$