Jelefy spelar Tornen i Hanoi med en särskild regel.

Tornen i Hanoi har tre pelare, $A$, $B$ och $C$, på vilka skivor kan staplas. Skivor kan flyttas mellan olika pelare, men måste följa följande regler:

• Endast en skiva får flyttas åt gången;
• Varje drag får endast flytta den översta skivan från en pelare till toppen av en annan pelare;
• På pelarna $B$ och $C$ får ingen skiva placeras ovanpå en mindre skiva;
• På pelare $A$ får större skivor placeras ovanpå mindre skivor.

I början staplar Jelefy slumpmässigt $n$ skivor av olika storlekar på pelare $A$ och lämnar pelarna $B$ och $C$ tomma. Under ovanstående villkor vill Jelefy veta hur många drag som behövs för att flytta alla skivor från pelare $A$ till pelare $B$.

Indata

Den första raden innehåller ett heltal $T$ ($1\leq T\leq 10^4$), som anger antalet testfall.

För varje testfall: Den första raden innehåller ett heltal $n$ ($1\leq n\leq 10^5$), som anger antalet skivor på pelare $A$ i startläget.

Den andra raden innehåller $n$ heltal $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), där $p_i$ anger diametern på den $i$-te skivan på pelare $A$ nerifrån och upp. Det garanteras att $p_1,p_2,\ldots,p_n$ utgör en permutation av längd $n$, det vill säga att varje heltal från $1$ till $n$ förekommer exakt en gång i följden.

För alla testfall garanteras att $\sum n\leq 2\times 10^5$.

Utdata

För varje testfall, skriv ut ett heltal på en egen rad som anger det minsta antalet drag som krävs.

Exempel

Indata 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

Förklaring

I det första exemplet ser en möjlig lösning med minsta antal drag ut så här ($X\rightarrow Y$ anger att den översta skivan på pelare $X$ flyttas till toppen av pelare $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$