Description

汉诺塔的游戏相信大家都玩过，这次又是一个汉诺塔。 有n根柱子，把数字从1开始按顺序一个个的放到柱子上去，先放1，再放2.依次类推。要求柱子上任意相邻两个数字之和都要是完全平方数，问n根柱子最多可以放几个数。

Input

第一行是一个整数T,表示输入数据的组数。 接下来T行，每行一个数n，表示有n根柱子(n <= 50)

Output

输出T行，每行一个整数，表示最多能放多少个数

Sample

Input

4
1
2
3
4

Output

1
3
7
11

Source: tty