Jelefy đang chơi trò Tháp Hà Nội với một quy tắc đặc biệt.

Tháp Hà Nội có ba cọc $A$, $B$ và $C$, trên đó có thể xếp chồng các đĩa. Các đĩa có thể được di chuyển giữa các cọc khác nhau, nhưng phải tuân thủ các quy tắc sau:

• Mỗi lần chỉ được di chuyển một đĩa;
• Mỗi bước chỉ được di chuyển đĩa nằm trên cùng của một cọc sang đỉnh của một cọc khác;
• Trên hai cọc $B$ và $C$, không đĩa nào được đặt lên trên một đĩa nhỏ hơn;
• Trên cọc $A$, các đĩa lớn hơn có thể được đặt lên trên các đĩa nhỏ hơn.

Ban đầu, Jelefy xếp ngẫu nhiên $n$ đĩa có kích thước khác nhau lên cọc $A$ và để trống hai cọc $B$ và $C$. Với các điều kiện trên, Jelefy muốn biết cần bao nhiêu bước di chuyển để chuyển toàn bộ các đĩa từ cọc $A$ sang cọc $B$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1\leq T\leq 10^4$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu: Dòng đầu tiên chứa một số nguyên $n$ ($1\leq n\leq 10^5$), biểu thị số lượng đĩa trên cọc $A$ ở trạng thái ban đầu.

Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$), trong đó $p_i$ biểu thị đường kính của đĩa thứ $i$ trên cọc $A$ tính từ dưới lên trên. Dữ liệu đảm bảo rằng $p_1,p_2,\ldots,p_n$ tạo thành một hoán vị độ dài $n$, tức là mỗi số nguyên từ $1$ đến $n$ xuất hiện đúng một lần trong dãy.

Đối với tất cả các bộ dữ liệu, đảm bảo rằng $\sum n\leq 2\times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một số nguyên trên một dòng duy nhất, biểu thị số bước di chuyển tối thiểu cần thiết.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

11
5
19

Ghi chú

Trong ví dụ đầu tiên, một cách giải khả dĩ với số bước di chuyển tối thiểu như sau ($X\rightarrow Y$ biểu thị việc di chuyển đĩa trên cùng từ cọc $X$ sang đỉnh của cọc $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$