---

题意整理

• 环编号从右到左是 (1, 2, \dots, n)（右边是最小号）。
• 规则：
  1. 第 1 个环（最右边）任何时候可以装上或卸下。
  2. 对于 (k \ge 1)，如果第 (k) 个环在剑上（即 1），且第 (k) 个环右边所有环都是卸下的（即 0），那么第 (k+1) 个环可以装上或卸下。
• 初始状态：所有环在剑上（全是 1）。
• 目标状态：所有环卸下（全是 0）。
• 求最少步数。

---

第一步：理解规则

规则 2 可解释为： 要操作第 (k+1) 个环，需要：

• 第 (k) 个环在剑上（值为 1）。
• 第 (1) 到 (k-1) 个环都是卸下的（值为 0）。

因此，操作第 (k+1) 环时，状态形如：
(X\ 1\ 0\ 0\ \dots\ 0)（第 (k+1) 环是 (X)，第 (k) 环是 1，右边全是 0）。

---

第二步：建立递推关系

设 (f_n) 表示将 (n) 连环从 全 1 变成 全 0 的最少步数。
设 (g_n) 表示将 (n) 连环从 全 1 变成 第 n 环为 0，其余全 1（即状态 (0\ 1\ 1\dots 1)）的最少步数。
这里环的编号从左到右是 (n, n-1, \dots, 1)（最左是第 n 环）。

我们统一：

• 状态是长度为 (n) 的二进制串，下标 1 是最右环。
• 初始：(111\dots1)。
• 目标：(000\dots0)。

---

从规则推 (f_n)

要卸下第 (n) 环（最左边），根据规则 2，需要：

• 第 (n-1) 环在剑上（1）。
• 第 (1) 到 (n-2) 环全卸下（0）。

所以先要把前 (n-1) 个环从全 1 变成状态：第 (n-1) 环为 1，其余 1 到 (n-2) 环为 0。

---

定义

令 (A_n)：将前 (n) 个环从全 1 变成全 0 的步数（即 (f_n)）。
令 (B_n)：将前 (n) 个环从全 1 变成 第 (n) 环为 0，其余 (n-1) 个环为 1 的步数。

---

我们要从 (111...1)（n 个）到 (000...0)（n 个）：

步骤：

1. 先将前 (n-1) 个环变成状态 (011...1)（即第 (n-1) 环是 1，其余 1 到 (n-2) 环是 0），这其实就是要得到第 (n-1) 环为 1，右边全 0，才能操作第 (n) 环。 但是要变成第 (n-1) 环为 1，右边全 0，相当于对前 (n-1) 个环执行某种操作。

   更准确：要操作第 (n) 环，需要状态：
   前 (n-1) 个环的状态是：第 (n-1) 环 = 1，第 (1..n-2) 环 = 0。

   这个状态怎么达到？
   先考虑前 (n-1) 个环：它们初始全 1，目标是要变成 (0 0 ... 0 1)（第 n-1 环是 1，右边全 0）。
   这就是 (B_{n-1})。

   所以第一步：用 (B_{n-1}) 步把前 (n-1) 环变成 (0...01)（第 n-1 环是 1）。

2. 现在状态是：第 n 环=1，前 n-1 环是 (0...01)，符合规则 2，可以卸下第 n 环（操作一步）。
   卸下后，状态变成：第 n 环=0，前 n-1 环还是 (0...01)。

3. 此时要再把前 n-1 个环从 (0...01) 变成全 0。
   但注意 (0...01)（第 n-1 环是 1，右边全 0）要变成全 0，需要先卸下第 n-1 环，而卸下第 n-1 环需要第 n-2 环为 1 且右边全 0，所以又需要先调整前 n-2 环…… 这正好是 (B_{n-1}) 的逆过程？
   实际上，从 (0...01) 到全 0 的步数就是 (B_{n-1})（因为对称性，装上与卸下步数相同）。

---

于是： [ A_n = B_{n-1} + 1 + B_{n-1} = 2 B_{n-1} + 1 ]

---

第三步：求 (B_n)

(B_n)：从全 1（n 个）变成第 n 环为 0，其余 n-1 个环为 1（即状态 (0\ 1\ 1\dots 1)，注意这里最左是第 n 环）。

步骤：

1. 要卸下第 n 环，需要前 n-1 环的状态为：第 n-1 环=1，第 1..n-2 环=0。
   这又需要先对前 n-1 个环用 (B_{n-1}) 步变成 (0...01)（第 n-1 环=1）。
2. 卸下第 n 环（一步），状态变成：第 n 环=0，前 n-1 环是 (0...01)。
3. 现在要把前 n-1 环从 (0...01) 变成全 1（n-1 个）。
   从 (0...01) 到全 1，需要先装上第 n-2 环等，这其实是 (B_{n-1}) 的“逆”过程，但步数和 (B_{n-1}) 相同吗？
   我们验证：从 (0...01)（第 n-1 环=1，右边全 0）到全 1（n-1 个 1），需要装上第 1..n-2 环。
   而装上第 k 环需要第 k-1 环为 1 且右边全 0，所以这恰好是 (B_{n-2}, B_{n-3}, \dots) 的和？其实可以直接用 (A_{n-1}) 吗？不，A 是从全 1 到全 0，我们这是从 (0...01) 到全 1。

---

实际上我们可以直接建立 (B_n) 的递推：

设状态 S1 = 全 1（n 个）
目标 S2 = 第 n 环=0，其余 n-1 环=1

记 (B_n) 为此过程步数。

从 S1 到 S2：

• 先对前 n-1 个环变成 (0...01)（第 n-1 环=1），这需要 (B_{n-1}) 步。

• 然后卸下第 n 环（一步），现在前 n-1 环是 (0...01)，第 n 环=0。

• 最后将前 n-1 环从 (0...01) 变成全 1（n-1 个）。
  从 (0...01)（第 n-1 环=1，右边全 0）到全 1：
  我们要装上第 1..n-2 环。这相当于对前 n-2 个环从全 0 变成全 1（n-2 个 1），同时保持第 n-1 环=1。

  对前 n-2 个环从全 0 到全 1，等价于对前 n-2 个环从全 1 到全 0 的逆过程，步数相同 = (A_{n-2})。

  所以这一步需要 (A_{n-2}) 步。

因此： [ B_n = B_{n-1} + 1 + A_{n-2} ]

---

第四步：联立方程

我们有： [ A_n = 2 B_{n-1} + 1 \quad (1) ] [ B_n = B_{n-1} + 1 + A_{n-2} \quad (2) ]

从 (1) 得 (B_{n-1} = \frac{A_n - 1}{2})。

代入 (2)： [ B_n = \frac{A_n - 1}{2} + 1 + A_{n-2} ] 即 [ B_n = \frac{A_n + 1}{2} + A_{n-2} ]

但 (B_n) 也满足 (1) 的 n+1 形式：
(A_{n+1} = 2 B_n + 1)。

代入 (B_n)： [ A_{n+1} = 2\left( \frac{A_n + 1}{2} + A_{n-2} \right) + 1 ] [ A_{n+1} = A_n + 1 + 2 A_{n-2} + 1 ] [ A_{n+1} = A_n + 2 A_{n-2} + 2 ]

更方便直接用 (A) 消去 (B)：

从 (1) 有 (B_{n-1} = \frac{A_n - 1}{2})，(B_{n-2} = \frac{A_{n-1} - 1}{2})。

代入 (2) 的 n-1 形式： [ B_{n-1} = B_{n-2} + 1 + A_{n-3} ] [ \frac{A_n - 1}{2} = \frac{A_{n-1} - 1}{2} + 1 + A_{n-3} ] 两边乘 2： [ A_n - 1 = A_{n-1} - 1 + 2 + 2 A_{n-3} ] [ A_n = A_{n-1} + 2 A_{n-3} + 2 ]

这就是 (A_n) 的递推式。

---

第五步：初始值

手动计算小 n：

• (n=1)：从 1 到 0，只需一步卸下环 1。(A_1 = 1)。
• (n=2)：
  初始 11
  卸下环 1（10）
  卸下环 2（00）
  两步？不对，规则 2：要卸下环 2，需要环 1 在剑上且环 1 右边全 0（环 1 是最右，右边无环），所以可以直接卸环 2？
  仔细：规则 2 中 k=1，第 1 环在剑上，第 1 环右边所有环（没有）都是卸下，所以第 2 环可卸。
  所以 11 → 01（卸环 2）→ 00（卸环 1），共 2 步。
  等等，样例 n=3 输出 5，验证：
  n=3：111 → 110（卸环 2）→ 100（卸环 1）→ 101（装环 1）→ 001（卸环 2）→ 000（卸环 1），共 6 步？但样例给 5。
  我可能步骤多余，看样例解释：
  样例 n=3 输出 5，我们验证已知公式：

已知标准九连环公式： [ f_n = \begin{cases} 1, & n=1 \ 2, & n=2 \ 2f_{n-1} + 1, & n \text{ 奇数} \ 2f_{n-1}, & n \text{ 偶数} \end{cases} ] 但这是错吗？我们验 n=3：
按奇数公式：2×2+1=5，对。
n=4：偶数，2×5=10，对（题目四连环例子 10 步）。
n=5：2×10+1=21，对样例。
n=9：递推上去 341，对样例。

所以标准公式是： [ f_n = \begin{cases} 2 f_{n-1} + 1, & n \text{ 奇数} \ 2 f_{n-1}, & n \text{ 偶数} \end{cases} ] (f_1 = 1)。

---

第六步：通项公式

从递推：

• 当 (n) 为奇数：(f_n = 2 f_{n-1} + 1)，(f_{n-1}) 是偶数情况：(f_{n-1} = 2 f_{n-2})，所以 (f_n = 4 f_{n-2} + 1)。
• 当 (n) 为偶数：(f_n = 2 f_{n-1})，(f_{n-1}) 是奇数：(f_{n-1} = 2 f_{n-2} + 1)，所以 (f_n = 4 f_{n-2} + 2)。

初始 (f_1=1, f_2=2)。

解递推： 对奇数 n=2k-1：
(f_{2k-1} = 4 f_{2k-3} + 1)，特征根 4，特解常数 -1/3？
设 (g_k = f_{2k-1})，则 (g_k = 4 g_{k-1} + 1)，(g_1=1)。
解得 (g_k = \frac{4^k - 1}{3})。

对偶数 n=2k：
(f_{2k} = 4 f_{2k-2} + 2)，设 (h_k = f_{2k})，则 (h_k = 4 h_{k-1} + 2)，(h_1=2)。
解得 (h_k = \frac{2 \cdot 4^k - 2}{3})。

---

合并： [ f_n = \begin{cases} \frac{2^{n+1} - 1}{3}, & n \text{ 奇数} \ \frac{2^{n+1} - 2}{3}, & n \text{ 偶数} \end{cases} ] 因为 (4^k = 2^{2k})，代入上面公式即可得到此形式。

---

检查 n=3（奇数）：(2^{4}=16)，(\frac{16-1}{3}=5) 对。
n=4（偶数）：(2^{5}=32)，(\frac{32-2}{3}=10) 对。

---

第七步：最终算法

对每个 n，直接按公式计算：

• 若 n 奇数，(f_n = \frac{2^{n+1} - 1}{3})。
• 若 n 偶数，(f_n = \frac{2^{n+1} - 2}{3})。

由于 n 可达 (10^5)，结果会很大，题目没有取模，所以可能需要高精度（大数运算）。

---

第八步：输出

对每个测试用例，用高精度计算并输出 (f_n)。

---

最终公式： [ \boxed{f_n = \left\lfloor \frac{2^{n+1}}{3} \right\rfloor} ] 因为：

• 奇数时 (\frac{2^{n+1}-1}{3} = \lfloor \frac{2^{n+1}}{3} \rfloor)
• 偶数时 (\frac{2^{n+1}-2}{3} = \lfloor \frac{2^{n+1}}{3} \rfloor)

统一为： [ f_n = \left\lfloor \frac{2^{n+1}}{3} \right\rfloor ]