Jelefy sedang bermain Menara Hanoi dengan aturan khusus.

Menara Hanoi memiliki tiga tiang, $A$, $B$, dan $C$, yang dapat digunakan untuk menumpuk cakram. Cakram dapat dipindahkan antar tiang yang berbeda, tetapi harus mematuhi aturan berikut:

• Hanya satu cakram yang dapat dipindahkan dalam satu waktu;
• Setiap langkah hanya dapat memindahkan cakram paling atas dari satu tiang ke bagian paling atas tiang lainnya;
• Pada tiang $B$ dan $C$, tidak ada cakram yang boleh diletakkan di atas cakram yang lebih kecil;
• Pada tiang $A$, cakram yang lebih besar boleh diletakkan di atas cakram yang lebih kecil.

Pada awalnya, Jelefy menumpuk $n$ cakram dengan ukuran berbeda secara acak pada tiang $A$ dan membiarkan tiang $B$ serta $C$ kosong. Berdasarkan ketentuan di atas, Jelefy ingin mengetahui berapa banyak langkah yang diperlukan untuk memindahkan semua cakram dari tiang $A$ ke tiang $B$.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1\leq T\leq 10^4$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji: Baris pertama berisi sebuah bilangan bulat $n$ ($1\leq n\leq 10^5$), yang menyatakan banyaknya cakram pada tiang $A$ pada keadaan awal.

Baris kedua berisi $n$ bilangan bulat $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), dengan $p_i$ menyatakan diameter cakram ke-$i$ pada tiang $A$ dari bawah ke atas. Dijamin bahwa $p_1,p_2,\ldots,p_n$ membentuk suatu permutasi sepanjang $n$, yaitu setiap bilangan bulat dari $1$ hingga $n$ muncul tepat satu kali dalam barisan tersebut.

Untuk semua kasus uji, dijamin bahwa $\sum n\leq 2\times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat pada satu baris tersendiri, yang menyatakan jumlah langkah minimum yang diperlukan.

Contoh

Masukan 1

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

Keluaran 1

11
5
19

Penjelasan

Pada contoh pertama, salah satu solusi yang mungkin dengan jumlah langkah minimum adalah sebagai berikut ($X\rightarrow Y$ menunjukkan pemindahan cakram paling atas dari tiang $X$ ke bagian paling atas tiang $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$