题目大意：经典汉诺塔问题的变形，现在给定四根柱子的汉诺塔，要求回答给定的初始塔高度，移动到到一根柱子所需要的操作次数。
思路分析：首先分析三根柱子的汉诺塔：将第 i − 1 i - 1 i−1个盘子从 a a a柱通过三根柱子移动到 b b b柱，然后将最大的移动到 c c c柱，最后又将 i − 1 i - 1 i−1个盘子通过三根柱子移动到 c c c柱。在这个过程中的操作次数为 d p [ i ] = 2 × d p [ i − 1 ] + 1 dp[i] = 2 \times dp[i - 1] + 1 dp[i]=2×dp[i−1]+1。
那么我们继续分析四根柱子的汉诺塔：
1、从A借助C、D将
n
−
2
n-2
n−2个盘子移动到B上； 2、将第
n
−
1
n-1
n−1个盘子移动到C上； 3、将第
n
n
n个盘子移动到D上； 4、将第
n
−
1
n-1
n−1个盘子移动到D上； 5、从B借助A、C将
n
−
2
n-2
n−2个盘子全部移动到D上。
以上是我们的基本思路。但是这并不是最优解。在盘子较少时是显然成立的，但盘子增多时，那些多余的只有一个盘子的柱子是可以加以利用的。因此我们需要一个更合理的算法：（参考四柱加强版汉诺塔HanoiTower）
1、用 4 4 4柱汉诺塔算法把A柱上部分的 n − r n- r n−r个碟子通过C柱和D柱移到B柱上【 F ( n − r ) F( n- r ) F(n−r)步】； 2、用 3 3 3柱汉诺塔经典算法把A柱上剩余的r个碟子通过C柱移到D柱上【 2 r − 1 2^r-1 2r−1步】（参照上述三柱时的情况）； 3、用 4 4 4柱汉诺塔算法把B柱上的 n − r n-r n−r个碟子通过A柱和C柱移到D柱上【 F ( n − r ) F(n-r) F(n−r)步】； 4、依据上边规则求出所有 r （ 1 ≤ r ≤ n r（1≤r≤n r（1≤r≤n）情况下步数 f ( n ) f(n) f(n)，取最小值得最终解。
因此可得状态转移方程： F ( n ) = m i n ( 2 × F ( n − r ) + 2 r − 1 ) , ( 1 ≤ r ≤ n ) F(n)=min(2 \times F(n-r)+2^r-1),(1≤r≤n) F(n)=min(2×F(n−r)+2r−1),(1≤r≤n)
但是这题还没完，数据范围要求我们不得不使用高精度算法。赛时没有考虑到高精度的问题。。。。。所以 P y h t o n Pyhton Pyhton牛逼。。。。
ans = [0 for i in range(10005)]
a = [0 for i in range(10005)]
def solve():
n = int(input())
print(ans[n])
def init():
ans[1], ans[2], ans[3] = 1, 3, 5
a[2], a[3] = 4, 8
cnt = 2
for i in range(4, 10001):
ans[i] = ans[i - cnt] * 2 + a[cnt] - 1
a[i] = 2 * a[i - 1]
if(ans[i] > ans[i - cnt - 1] * 2 + a[cnt + 1] - 1):
cnt = cnt + 1
ans[i] = ans[i - cnt] * 2 + a[cnt] - 1
if __name__ == "__main__":
init()
t = int(input())
while t:
solve()
t -= 1
