Jelefy joue aux Tours de Hanoï avec une règle spéciale.

Les Tours de Hanoï comportent trois piliers, $A$, $B$ et $C$, sur lesquels des disques peuvent être empilés. Les disques peuvent être déplacés entre différents piliers, mais doivent respecter les règles suivantes :

• Un seul disque peut être déplacé à la fois ;
• Chaque coup ne peut déplacer que le disque situé au sommet d'un pilier vers le sommet d'un autre pilier ;
• Sur les piliers $B$ et $C$, aucun disque ne peut être placé au-dessus d'un disque plus petit ;
• Sur le pilier $A$, des disques plus grands peuvent être placés au-dessus de disques plus petits.

Au début, Jelefy empile aléatoirement $n$ disques de tailles différentes sur le pilier $A$ et laisse les piliers $B$ et $C$ vides. Dans les conditions ci-dessus, Jelefy veut savoir combien de coups sont nécessaires pour déplacer tous les disques du pilier $A$ vers le pilier $B$.

Entrée

La première ligne contient un entier $T$ ($1\leq T\leq 10^4$), indiquant le nombre de cas de test.

Pour chaque cas de test : La première ligne contient un entier $n$ ($1\leq n\leq 10^5$), représentant le nombre de disques sur le pilier $A$ dans l'état initial.

La deuxième ligne contient $n$ entiers $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), où $p_i$ représente le diamètre du $i$-ème disque sur le pilier $A$ de bas en haut. Il est garanti que $p_1,p_2,\ldots,p_n$ forment une permutation de longueur $n$, c'est-à-dire que chaque entier de $1$ à $n$ apparaît exactement une fois dans la suite.

Pour tous les cas de test, il est garanti que $\sum n\leq 2\times 10^5$.

Sortie

Pour chaque cas de test, affichez un entier sur une seule ligne, représentant le nombre minimal de coups requis.

Exemples

Entrée 1

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

Sortie 1

11
5
19

Remarque

Dans le premier exemple, une solution possible utilisant le nombre minimal de coups est la suivante ($X\rightarrow Y$ indique le déplacement du disque au sommet du pilier $X$ vers le sommet du pilier $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$