题目描述

Natsuzora 在玩一个特殊规则的汉诺塔。

汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则：

• 一次只有一个圆盘被移动；
• 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端；
• 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上；
• 在柱子 $A$ 上，允许将较大的圆盘放置在较小的圆盘上。

最开始时，Natsuzora 将 $n$ 个大小互不相同的圆盘乱序地摞在 $A$ 柱子上并将柱子 $B$ 和 $C$ 留空。在满足上述条件的情况下，Natsuzora 想要知道，若要将 $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$。

输出格式

对于每组数据，输出一行一个整数，表示需要的最少移动次数。

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

11
5
19

提示

在第一个样例中，一种可行的次数最少的移动方案如下（$X\rightarrow Y$ 表示将柱子 $X$ 最顶上的圆盘移动到柱子 $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$