Jelefy pelaa Hanoin tornia erikoissäännöllä.

Hanoin tornissa on kolme pylvästä, $A$, $B$ ja $C$, joihin kiekkoja voidaan pinota. Kiekkoja voidaan siirtää pylväältä toiselle, mutta seuraavia sääntöjä on noudatettava:

• Kerrallaan saa siirtää vain yhden kiekon;
• Jokaisella siirrolla saa siirtää vain yhden pylvään päällimmäisen kiekon toisen pylvään päälle;
• Pylväissä $B$ ja $C$ mitään kiekkoa ei saa asettaa pienemmän kiekon päälle;
• Pylväässä $A$ suurempia kiekkoja saa asettaa pienempien kiekkojen päälle.

Aluksi Jelefy pinoaa satunnaisesti $n$ erikokoista kiekkoa pylvääseen $A$ ja jättää pylväät $B$ ja $C$ tyhjiksi. Yllä olevilla ehdoilla Jelefy haluaa tietää, kuinka monta siirtoa tarvitaan kaikkien kiekkojen siirtämiseksi pylväästä $A$ pylvääseen $B$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1\leq T\leq 10^4$), joka ilmoittaa testitapausten lukumäärän.

Jokaiselle testitapaukselle: Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1\leq n\leq 10^5$), joka kuvaa pylväässä $A$ alkutilanteessa olevien kiekkojen lukumäärää.

Toinen rivi sisältää $n$ kokonaislukua $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), missä $p_i$ kuvaa pylväässä $A$ alhaalta ylös laskettuna $i$:nnen kiekon halkaisijaa. On taattu, että $p_1,p_2,\ldots,p_n$ muodostavat pituuden $n$ permutaation, eli jokainen kokonaisluku väliltä $1$–$n$ esiintyy jonossa täsmälleen kerran.

Kaikkien testitapausten yli on taattu, että $\sum n\leq 2\times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden omalle rivilleen yksi kokonaisluku, joka ilmaisee pienimmän tarvittavan siirtojen määrän.

Esimerkki

Syöte 1

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

Tuloste 1

11
5
19

Selitys

Ensimmäisessä esimerkissä yksi mahdollinen ratkaisu pienimmällä siirtomäärällä on seuraava ($X\rightarrow Y$ tarkoittaa päällimmäisen kiekon siirtämistä pylväästä $X$ pylvään $Y$ päälle):

• $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$