#1300. 「CQOI2018」九连环

「CQOI2018」九连环

题目描述

九连环是一种源于中国的传统智力游戏。如图所示,九个圆环套在一把“剑”上,并且互相牵连。游戏的目标是把九个圆环从“剑”上卸下。

无标题.png

圆环的装卸需要遵守两个规则。

  1. 第一个(最右边)环任何时候都可以装上或卸下。
  2. 如果第 kk 个环没有被卸下,且第 kk 个环右边的所有环都被卸下,则第 k+1k+1 个环(第 kk 个环左边相邻的环)可以任意装上或卸下。

与魔方的千变万化不同,解九连环的最优策略是唯一的。为简单起见,我们以“四连环”为例,演示这一过程。这里用 1 表示环在“剑”上, 0 表示环已经卸下。

初始状态为 1111 ,每部的操作如下:

  1. 1101 (根据规则 22 ,卸下第 22 个环)
  2. 1100 (根据规则 11 ,卸下第 11 个环)
  3. 0100 (根据规则 22 ,卸下第 44 个环)
  4. 0101 (根据规则 11 ,装上第 11 个环)
  5. 0111 (根据规则 22 ,装上第 22 个环)
  6. 0110 (根据规则 11 ,卸下第 11 个环)
  7. 0010 (根据规则 22 ,卸下第 33 个环)
  8. 0011 (根据规则 11 ,装上第 11 个环)
  9. 0001 (根据规则 22 ,卸下第 22 个环)
  10. 0000 (根据规则 11 ,卸下第 11 个环)

由此可见,卸下“四连环”至少需要 1010 步。随着环数增加,需要的步数也会随之增多。例如卸下九连环,就至少需要 341341 步。
请你计算,有 nn 个环的情况下,按照规则,全部卸下至少需要多少步。

输入格式

输入第一行为一个整数 mm ,表示测试点数目。
接下来 mm 行,每行一个整数 nn

输出格式

输出共 mm 行,对应每个测试点的计算结果。

样例

3
3
5
9
5
21
341

数据范围与提示

对于 10%10\% 的数据, 1n101 \le n \le 10
对于 30%30\% 的数据, 1n301 \le n \le 30
对于 100%100\% 的数据, 1n105,1m101 \le n \le 10^5 , 1 \le m \le 10