#2535. 「CQOI2018」九连环

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

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

无标题.png

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

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

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

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

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

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

输入格式

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

输出格式

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

样例

样例输入

3
3
5
9

样例输出

5
21
341

数据范围与提示

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