Jelefy er að spila Turnana í Hanoi með sérstakri reglu.

Turnarnir í Hanoi hafa þrjár súlur, $A$, $B$ og $C$, sem hægt er að stafla skífum á. Hægt er að færa skífur á milli ólíkra súlna, en fylgja verður eftirfarandi reglum:

• Aðeins má færa eina skífu í einu;
• Í hverjum leik má aðeins færa efstu skífuna af einni súlu efst á aðra súlu;
• Á súlum $B$ og $C$ má engin skífa fara ofan á minni skífu;
• Á súlu $A$ má setja stærri skífur ofan á minni skífur.

Í upphafi staflar Jelefy $n$ misstórum skífum af handahófi á súlu $A$ og lætur súlur $B$ og $C$ vera tómar. Við ofangreind skilyrði vill Jelefy vita hve marga leiki þarf til að færa allar skífurnar af súlu $A$ yfir á súlu $B$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1\leq T\leq 10^4$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik: Fyrsta línan inniheldur heiltölu $n$ ($1\leq n\leq 10^5$), sem táknar fjölda skífa á súlu $A$ í upphafsstöðunni.

Önnur línan inniheldur $n$ heiltölur $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), þar sem $p_i$ táknar þvermál $i$-tu skífunnar á súlu $A$ neðan frá og upp. Tryggt er að $p_1,p_2,\ldots,p_n$ myndi umröðun af lengd $n$, þ.e. hver heiltala frá $1$ til $n$ kemur nákvæmlega einu sinni fyrir í rununni.

Fyrir öll prófunartilvik er tryggt að $\sum n\leq 2\times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal skrifa út eina heiltölu á eigin línu, sem táknar lágmarksfjölda leikja sem þarf.

Dæmi

Inntak 1

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

Úttak 1

11
5
19

Skýring

Í fyrsta dæminu er ein möguleg lausn með lágmarksfjölda leikja sem hér segir ($X\rightarrow Y$ táknar að færa efstu skífuna af súlu $X$ efst á súlu $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$