题目背景

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

题目描述

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

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≤n≤10$

对于30%的数据，$1≤n≤30$

对于100%的数据，$1≤n≤10^5,1≤m≤10$