Jelefy spiller Tårnene i Hanoi med en spesiell regel.

Tårnene i Hanoi har tre søyler, $A$, $B$ og $C$, som skiver kan stables på. Skiver kan flyttes mellom ulike søyler, men må følge disse reglene:

• Bare én skive kan flyttes om gangen;
• Hvert trekk kan bare flytte den øverste skiven på én søyle til toppen av en annen søyle;
• På søylene $B$ og $C$ kan ingen skive plasseres oppå en mindre skive;
• På søyle $A$ kan større skiver plasseres oppå mindre skiver.

Til å begynne med stabler Jelefy tilfeldig $n$ skiver av ulik størrelse på søyle $A$ og lar søylene $B$ og $C$ stå tomme. Under betingelsene ovenfor vil Jelefy vite hvor mange trekk som trengs for å flytte alle skivene fra søyle $A$ til søyle $B$.

Inndata

Den første linjen inneholder et heltall $T$ ($1\leq T\leq 10^4$), som angir antall testtilfeller.

For hvert testtilfelle: Den første linjen inneholder et heltall $n$ ($1\leq n\leq 10^5$), som representerer antall skiver på søyle $A$ i starttilstanden.

Den andre linjen inneholder $n$ heltall $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), der $p_i$ representerer diameteren til den $i$-te skiven på søyle $A$ nedenfra og opp. Det garanteres at $p_1,p_2,\ldots,p_n$ utgjør en permutasjon av lengde $n$, dvs. at hvert heltall fra $1$ til $n$ forekommer nøyaktig én gang i følgen.

For alle testtilfellene garanteres det at $\sum n\leq 2\times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut et heltall på en egen linje, som representerer det minste antallet trekk som kreves.

Eksempel

Inndata 1

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

Utdata 1

11
5
19

Forklaring

I det første eksempelet er én mulig løsning med færrest mulig trekk som følger ($X\rightarrow Y$ betyr å flytte den øverste skiven fra søyle $X$ til toppen av søyle $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$