The Capacity of Square-Sum Stacks¶
Estimated time limit: 0.5 seconds. Memory limit: 128 MB.
The limit is twice the slowest median runtime of the reference program, rounded up to a multiple of \(0.5\) seconds. See the evaluation environment.
Story¶
Magic balls have consecutive labels starting at one, with one ball of each label. A new ball may be placed on a nonempty stack only when its label and the current top label sum to a perfect square. Any ball may start an empty stack.
Formal Problem Statement¶
Each test case gives a stack count \(N\) . Place balls in the order \(1,2,3,\ldots\) , without skipping labels or moving previously placed balls. A ball may start an empty stack or be placed on a top ball whose label sums with its own label to a perfect square.
Find the maximum number of balls that can be placed. Print the exact answer, without taking a modulus.
Input Format¶
The first line contains \(T\) . Each of the next \(T\) lines contains one positive decimal integer \(N\) , describing an independent test case.
Output Format¶
Print \(T\) lines, with the exact decimal answer to each test case in order.
Samples¶
Sample 1¶
Input¶
1
4
Output¶
11
Sample 2¶
Input¶
4
1
2
3
5
Output¶
1
3
7
17
Sample 3¶
Input¶
1
100000000000000000000
Output¶
5000000000000000000099999999999999999999
Sample Explanation¶
Four stacks hold at most eleven balls; one arrangement appears below. The capacities of one, two, three and five stacks are one, three, seven and seventeen. The last case requires a large exact integer.
Constraints and Guarantees¶
\(1\le T\le1000\) , \(1\le N\le2\times10^{10^5}\) . The entire input text contains at most \(6\times10^5\) characters.
| Score | Additional constraints |
|---|---|
| 100% | None |