题目描述

同学们十分喜欢糖葫芦，他们发明了一种“糖葫芦游戏”。规则如下：在桌上有\(n\)根棍子，假设这些棍子的长度均为无限长。现在我们有无穷多的山楂，山楂被标号为\(1,2,3,…\)。现在，要求你把山楂插到棍子上。规则：按照山楂号码的先后顺序，先插\(1\)号山楂，然后插\(2\)号，\(……\)山楂一插到棍子上，就会落到棍子最上面的一颗山楂上面。在插山楂时，必须满足一个条件：在同一根棍子上，上下挨着的两颗山楂上的号码之和必须是一个完全平方数（不用考虑棍子上的第 \(1\) 颗山楂）。下面统计在桌子上有\(n\)根棍子时，最多能插多少颗山楂。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；接下来 \(t\) 行，每行仅一个整数 \(n(≤500)\)，表示棍子的总数。

输出格式

对于每组数据，输出最多的山楂数。

样例1

输入样例1

2
200
4

输出样例1

20199
11

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T1\)

文件IO

freopen("game.in","r",stdin);
freopen("game.out","w",stdout);