Jelefy は特別なルールを持つハノイの塔で遊んでいます。

ハノイの塔には $A$、$B$、$C$ の 3 本の柱があり、それぞれの柱に円盤を積み重ねることができます。円盤は異なる柱の間で移動させることができますが、以下のルールに従わなければなりません：

• 一度に移動できる円盤は 1 枚のみである；
• 各操作では、ある柱の一番上にある円盤を、別の柱の一番上にのみ移動できる；
• 柱 $B$ および柱 $C$ では、どの円盤もそれより小さい円盤の上に置くことはできない；
• 柱 $A$ では、大きい円盤を小さい円盤の上に置くことができる。

最初、Jelefy は大きさの異なる $n$ 枚の円盤を柱 $A$ にランダムに積み重ね、柱 $B$ と柱 $C$ は空のままにします。上記の条件のもとで、Jelefy はすべての円盤を柱 $A$ から柱 $B$ へ移動させるために必要な手数を知りたいと考えています。

入力

1 行目には、テストケースの個数を表す整数 $T$（$1\leq T\leq 10^4$）が与えられます。

各テストケースについて： 1 行目には、初期状態で柱 $A$ に積まれている円盤の枚数を表す整数 $n$（$1\leq n\leq 10^5$）が与えられます。

2 行目には、$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$ までの各整数がこの列にちょうど 1 回ずつ現れることが保証されます。

すべてのテストケースについて、$\sum n\leq 2\times 10^5$ であることが保証されます。

出力

各テストケースについて、必要な最小手数を表す整数を 1 行に出力してください。

入出力例

入力 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

注記

1 つ目の例において、手数が最小となる移動手順の一例は以下の通りです（$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$