The player should place one ball on the top of a peg at a time. He should first try ball 1, then ball 2, then ball 3... If he fails to do so, the game ends. Help the player to place as many balls as possible. You may take a look at the picture above, since it shows us a best result for 4 pegs.

Input

The first line of the input contains a single integer T, indicating the number of test cases. (1<=T<=50) Each test case contains a single integer N(1<=N<=50), indicating the number of pegs available.

Output

For each test case in the input print a line containing an integer indicating the maximal number of balls that can be placed. Print -1 if an infinite number of balls can be placed.

Sample Input

2
4
25

Sample Output

11
337

给出n个柱子，从第一个柱子开始放珠子，珠子编号从1开始，要求每个柱子上相邻两个珠子的和是可开方的。

#include<stdio.h>#include<math.h>#include<string.h>int a[55];int main(){    int t;    scanf("%d",&t);    while(t--)    {        memset(a,0,sizeof(a));        int n;        scanf("%d",&n);        int poit=1;        int s=1;        while(1)        {            if(poit>n)                break;            if(a[poit]==0)            {                a[poit]=s;                s++;                poit=1;                continue;            }            else            {                int b=a[poit]+s;                int c=sqrt(b);                if(c*c==b)                {                    a[poit]=s;                    s++;                    poit=1;                    continue;                }            }            poit++;        }        printf("%d\n",s-1);    }    return 0;}