# 平方和球柱的容量

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

魔法球依次编号为一、二、三，依此类推，每种编号恰好一个。你有若干根柱子，只有当新球与柱顶球的编号之和为完全平方数时，才能将它放到该柱顶；空柱可以直接放球。

## 形式化问题描述

每组数据给定柱子数 $N$ .按 $1,2,3,\ldots$ 的顺序放球，不能跳过编号或移动已放好的球。每次将新球放在空柱上，或放在一根柱顶编号与它相加为完全平方数的柱子顶端。

求最多能放入多少个球。答案必须精确输出，不取模。

## 输入格式

第一行一个整数 $T$ .随后 $T$ 行，每行一个十进制正整数 $N$ ，表示一组独立数据。

## 输出格式

输出 $T$ 行，每行一个十进制整数，依次表示对应数据的答案。

## 样例

### 样例 1

### 输入

```text
1
4
```

### 输出

```text
11
```

### 样例 2

### 输入

```text
4
1
2
3
5
```

### 输出

```text
1
3
7
17
```

### 样例 3

### 输入

```text
1
100000000000000000000
```

### 输出

```text
5000000000000000000099999999999999999999
```

## 样例解释

四根柱子最多放十一球，下面给出一种方案。一、二、三、五根柱子的容量分别为一、三、七、十七。最后一组说明答案需要使用高精度整数。

![N=4; adjacent labels sum to 9, 16 or 4](assets/stacks.svg)

## 数据范围与保证

$1\le T\le1000$ ，$1\le N\le2\times10^{10^5}$ .整个输入文本长度不超过 $6\times10^5$ 个字符。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |