平方和球柱的容量¶
预估时间限制：0.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
魔法球依次编号为一、二、三，依此类推，每种编号恰好一个。你有若干根柱子，只有当新球与柱顶球的编号之和为完全平方数时，才能将它放到该柱顶；空柱可以直接放球。
形式化问题描述¶
每组数据给定柱子数 \(N\) .按 \(1,2,3,\ldots\) 的顺序放球，不能跳过编号或移动已放好的球。每次将新球放在空柱上，或放在一根柱顶编号与它相加为完全平方数的柱子顶端。
求最多能放入多少个球。答案必须精确输出，不取模。
输入格式¶
第一行一个整数 \(T\) .随后 \(T\) 行，每行一个十进制正整数 \(N\) ，表示一组独立数据。
输出格式¶
输出 \(T\) 行，每行一个十进制整数，依次表示对应数据的答案。
样例¶
样例 1¶
输入¶
1
4
输出¶
11
样例 2¶
输入¶
4
1
2
3
5
输出¶
1
3
7
17
样例 3¶
输入¶
1
100000000000000000000
输出¶
5000000000000000000099999999999999999999
样例解释¶
四根柱子最多放十一球，下面给出一种方案。一、二、三、五根柱子的容量分别为一、三、七、十七。最后一组说明答案需要使用高精度整数。
数据范围与保证¶
\(1\le T\le1000\) ，\(1\le N\le2\times10^{10^5}\) .整个输入文本长度不超过 \(6\times10^5\) 个字符。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |