#P2113. 汉诺塔(四)

汉诺塔(四)

    汉诺塔问题是一个经典的问题,现在我们有 n 个柱子和 m 个编号(1~m)的球,我们现在要求把尽量多的球放在尽量少的柱子上,如果相邻两个球的和不是完全平方数的话球会相互排斥而无法接触。(注意:球必须从小到大放,每次只能放在其他球的上面或者一个新的柱子上面)

Input

首先一个T,表示T组测试数据,然后一个n(1<=n<=50).

Output

输出一行,表示n个柱子能放的最大的球编号。

Sample Input

1
4

Sample Output

11

HINT

Source