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$ 代表柱子 $A$ 上由下而上第 $i$ 個圓盤的直徑。保證 $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$