Jelefy грає в Ханойську вежу за особливим правилом.

Ханойська вежа має три стрижні $A$, $B$ та $C$, на які можна складати диски. Диски можна переміщувати між різними стрижнями, але необхідно дотримуватися таких правил:

• За один раз можна перемістити лише один диск;
• Кожен хід може перемістити лише верхній диск одного стрижня на верхівку іншого стрижня;
• На стрижнях $B$ та $C$ жоден диск не можна класти поверх меншого диска;
• На стрижні $A$ більші диски можна класти поверх менших дисків.

На початку Jelefy випадковим чином складає $n$ дисків різного розміру на стрижень $A$, залишаючи стрижні $B$ та $C$ порожніми. За наведених вище умов Jelefy хоче дізнатися, скільки ходів потрібно, щоб перемістити всі диски зі стрижня $A$ на стрижень $B$.

Вхідні дані

Перший рядок містить ціле число $T$ ($1\leq T\leq 10^4$), що позначає кількість наборів вхідних даних.

Для кожного набору вхідних даних: Перший рядок містить ціле число $n$ ($1\leq n\leq 10^5$), що позначає кількість дисків на стрижні $A$ у початковому стані.

Другий рядок містить $n$ цілих чисел $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), де $p_i$ позначає діаметр $i$-го диска на стрижні $A$ знизу вгору. Гарантується, що $p_1,p_2,\ldots,p_n$ утворюють перестановку довжини $n$, тобто кожне ціле число від $1$ до $n$ зустрічається в послідовності рівно один раз.

Для всіх наборів вхідних даних гарантується, що $\sum n\leq 2\times 10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть одне ціле число в окремому рядку — мінімальну необхідну кількість ходів.

Приклади

Вхідні дані 1

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

Вихідні дані 1

11
5
19

Примітка

У першому прикладі одне з можливих рішень із мінімальною кількістю ходів таке ($X\rightarrow Y$ позначає переміщення верхнього диска зі стрижня $X$ на верхівку стрижня $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$