A. Hanoi Sort
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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
Note

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$$$):

  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$$$