Problem Description

Natsuzora is playing a Tower of Hanoi with special rules.

There are three pegs, $A$, $B$, and $C$. Disks can be stacked on each peg. Disks may be moved between pegs, but the following rules must be followed:

• Only one disk can be moved at a time.
• Each move can only take the top disk of one peg and place it onto the top of another peg.
• On pegs $B$ and $C$, it is not allowed to place any disk on top of another disk that is smaller than it.
• On peg $A$, it is allowed to place a larger disk on top of a smaller disk.

At the beginning, Natsuzora stacks $n$ disks of distinct sizes in a random order on peg $A$, leaving pegs $B$ and $C$ empty. Under the rules above, Natsuzora wants to know the minimum number of moves needed to move all disks from peg $A$ to peg $B$.

Input Format

The first line contains an integer $T$ $(1\leq T\leq 10^4)$, representing the number of test cases.

For each test case, the first line contains an integer $n$ $(1\leq n\leq 10^5)$, representing the number of disks on peg $A$ in the initial state.

The second line of each test case contains $n$ integers $p_1,p_2,\ldots,p_n$ $(1\leq p_i\leq n)$, where $p_i$ is the diameter of the $i$-th disk on peg $A$ from bottom to top. The testdata guarantees that $p_1,p_2,\ldots,p_n$ is a permutation of length $n$, meaning each integer from $1$ to $n$ appears exactly once in the sequence.

For all test cases, it is guaranteed that $\sum n\leq 2\times 10^5$.

Output Format

For each test case, output one integer per line, representing the minimum number of moves required.

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

11
5
19

Hint

In the first sample, one feasible move sequence with the minimum number of moves is as follows ($X\rightarrow Y$ means moving the top disk of peg $X$ to the top of peg $Y$):

1. $A\rightarrow C$
2. $A\rightarrow B$
3. $A\rightarrow C$
4. $B\rightarrow C$
5. $A\rightarrow B$
6. $C\rightarrow A$
7. $C\rightarrow A$
8. $C\rightarrow B$
9. $A\rightarrow B$
10. $A\rightarrow B$
11. $A\rightarrow B$

Translated by ChatGPT 5