说明

大家对汉诺塔游戏已经很熟悉了吧？

那么，如果说盘子只能在相邻的柱子之间移动呢？

输入格式

第一行为一个数 T，为询问次数。

往后 T 行每行一个数 n(1 <= n <= 35)，为汉诺塔游戏中盘子的个数。

输出格式

T 行，每一行为对应询问中，把 n 个盘子从第 1 个柱子移动到第 3 个柱子所需要的最少的移动盘子的次数。

样例

2
3
12

26
531440