Jelefy is playing the Tower of Hanoi with a special rule.

The Tower of Hanoi has three pillars, $A$, $B$, and $C$, on which disks can be stacked. Disks can be moved between different pillars, but must adhere to the following rules:

• Only one disk can be moved at a time;
• Each move can only move the top disk of one pillar to the top of another pillar;
• On pillars $B$ and $C$, no disk can be placed on top of a smaller disk;
• On pillar $A$, larger disks can be placed on top of smaller disks.

At the beginning, Jelefy randomly stacks $n$ disks of different sizes on pillar $A$ and leaves pillars $B$ and $C$ empty. Under the above conditions, Jelefy wants to know how many moves are needed to move all the disks from pillar $A$ to pillar $B$.

Input

The first line contains an integer $T$ ($1\leq T\leq 10^4$), indicating 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 pillar $A$ in the initial state.

The second line contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), where $p_i$ represents the diameter of the $i$-th disk on pillar $A$ from bottom to top. It is guaranteed that $p_1,p_2,\ldots,p_n$ form a permutation of length $n$, i.e., 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

For each test case, output an integer on a single line, representing the minimum number of moves required.

Example

Input

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

Output

11
5
19

Explanation

In the first example, one possible solution with the minimum number of moves is as follows ($X\rightarrow Y$ indicates moving the top disk from pillar $X$ to the top of pillar $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$