{"raw_statement":[{"iden":"statement","content":"Natsuzora 在玩一个特殊规则的汉诺塔。\n\n汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则：\n\n- 一次只有一个圆盘被移动；\n- 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端；\n- 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上；\n- **在柱子 $A$ 上，允许将较大的圆盘放置在较小的圆盘上。**\n\n最开始时，Natsuzora 将 $n$ 个大小互不相同的圆盘乱序地摞在 $A$ 柱子上并将柱子 $B$ 和 $C$ 留空。在满足上述条件的情况下，Natsuzora 想要知道，若要将 $A$ 柱上的圆盘全部移动到 $B$ 柱上，他至少需要进行多少次移动。"},{"iden":"input","content":"第一行包含一个整数 $T$ $(1\\leq T\\leq 10^4)$，表示数据组数。\n\n每组数据的第一行包含一个整数 $n$ $(1\\leq n\\leq 10^5)$，表示初始状态下柱子 $A$ 上的圆盘数量。\n\n每组数据的第二行包含 $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$ 中的每个整数都在序列中出现恰好一次。\n\n对于所有数据，保证 $\\sum n\\leq 2\\times 10^5$。"},{"iden":"output","content":"对于每组数据，输出一行一个整数，表示需要的最少移动次数。"},{"iden":"note","content":"在第一个样例中，一种可行的次数最少的移动方案如下（$X\\rightarrow Y$ 表示将柱子 $X$ 最顶上的圆盘移动到柱子 $Y$ 的顶部）：\n\n  1. $A\\rightarrow C$\n  2. $A\\rightarrow B$\n  3. $A\\rightarrow C$\n  4. $B\\rightarrow C$\n  5. $A\\rightarrow B$\n  6. $C\\rightarrow A$\n  7. $C\\rightarrow A$\n  8. $C\\rightarrow B$\n  9. $A\\rightarrow B$\n  10. $A\\rightarrow B$\n  11. $A\\rightarrow B$"}],"translated_statement":null,"sample_group":[["3\n5\n1 5 3 2 4\n5\n1 2 3 4 5\n6\n5 3 6 1 4 2","11\n5\n19"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}