Jelefy está jugando a la Torre de Hanói con una regla especial.

La Torre de Hanói tiene tres pilares, $A$, $B$ y $C$, sobre los cuales se pueden apilar discos. Los discos se pueden mover entre diferentes pilares, pero deben cumplir las siguientes reglas:

• Solo se puede mover un disco a la vez;
• Cada movimiento solo puede trasladar el disco superior de un pilar a la parte superior de otro pilar;
• En los pilares $B$ y $C$, ningún disco puede colocarse encima de un disco más pequeño;
• En el pilar $A$, se pueden colocar discos más grandes encima de discos más pequeños.

Al principio, Jelefy apila aleatoriamente $n$ discos de diferentes tamaños en el pilar $A$ y deja vacíos los pilares $B$ y $C$. Bajo las condiciones anteriores, Jelefy quiere saber cuántos movimientos se necesitan para trasladar todos los discos del pilar $A$ al pilar $B$.

Entrada

La primera línea contiene un entero $T$ ($1\leq T\leq 10^4$), que indica el número de casos de prueba.

Para cada caso de prueba: La primera línea contiene un entero $n$ ($1\leq n\leq 10^5$), que representa el número de discos en el pilar $A$ en el estado inicial.

La segunda línea contiene $n$ enteros $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), donde $p_i$ representa el diámetro del $i$-ésimo disco en el pilar $A$ de abajo hacia arriba. Se garantiza que $p_1,p_2,\ldots,p_n$ forman una permutación de longitud $n$, es decir, cada entero de $1$ a $n$ aparece exactamente una vez en la secuencia.

Para todos los casos de prueba, se garantiza que $\sum n\leq 2\times 10^5$.

Salida

Para cada caso de prueba, imprima un entero en una sola línea, que represente el número mínimo de movimientos requeridos.

Ejemplos

Entrada 1

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

Salida 1

11
5
19

Nota

En el primer ejemplo, una posible solución con el número mínimo de movimientos es la siguiente ($X\rightarrow Y$ indica mover el disco superior del pilar $X$ a la parte superior del pilar $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$