Jelefy sta giocando alla Torre di Hanoi con una regola speciale.

La Torre di Hanoi ha tre pioli, $A$, $B$ e $C$, sui quali possono essere impilati dei dischi. I dischi possono essere spostati tra pioli diversi, ma devono rispettare le seguenti regole:

• È possibile spostare un solo disco alla volta;
• Ogni mossa può spostare solo il disco in cima a un piolo sulla cima di un altro piolo;
• Sui pioli $B$ e $C$, nessun disco può essere posizionato sopra un disco più piccolo;
• Sul piolo $A$, i dischi più grandi possono essere posizionati sopra i dischi più piccoli.

All'inizio, Jelefy impila casualmente $n$ dischi di dimensioni diverse sul piolo $A$ e lascia vuoti i pioli $B$ e $C$. Nelle condizioni sopra indicate, Jelefy vuole sapere quante mosse sono necessarie per spostare tutti i dischi dal piolo $A$ al piolo $B$.

Input

La prima riga contiene un intero $T$ ($1\leq T\leq 10^4$), che indica il numero di casi di test.

Per ogni caso di test: La prima riga contiene un intero $n$ ($1\leq n\leq 10^5$), che rappresenta il numero di dischi sul piolo $A$ nello stato iniziale.

La seconda riga contiene $n$ interi $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), dove $p_i$ rappresenta il diametro dell'$i$-esimo disco sul piolo $A$ dal basso verso l'alto. È garantito che $p_1,p_2,\ldots,p_n$ formino una permutazione di lunghezza $n$, cioè ogni intero da $1$ a $n$ appare esattamente una volta nella sequenza.

Per tutti i casi di test, è garantito che $\sum n\leq 2\times 10^5$.

Output

Per ogni caso di test, stampa un intero su una singola riga, che rappresenta il numero minimo di mosse necessarie.

Esempi

Input 1

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

Output 1

11
5
19

Nota

Nel primo esempio, una possibile soluzione con il numero minimo di mosse è la seguente ($X\rightarrow Y$ indica lo spostamento del disco in cima al piolo $X$ sulla cima del piolo $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$