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$