It is a well known fact that it's impossible to fill the plane with identical regular octagons, but the math mages didn't knew this till it was too late, they had already ordered an infinite number of them (And they only had to pay $$$-\frac{1}{12}$$$ dollars for them).
So, now, they want to try to fill the plane anyway! To do this they devised the following algorithm, they'll start by putting an octagone anywhere in the plane, they will call this octagon, octagon 0.
From octagon $$$0$$$, they choose one of its sides, and try to put another octagon next to it such that one of its faces coincide with the choosen face, this will be octagon $$$1$$$.
After that they will follow the next procedure:
- Let $$$n$$$ be the number of the last octagone that was put on the plane. From the side that coincides with the octagone $$$n-1$$$ we start trying to put octagone $$$n+1$$$ next to that side, if it is not possible, we try the next side counterclockwise, until it is possible to put a new octagone without overlapping another octagone that was put before.
It can be proven that this procedure allows you to put an infinite number of octagons in the plane.
Before starting, they want to know what is the squared distance from the center of octagone $$$k$$$ to the center of octagone $$$0$$$
The first line contains an integer $$$Q$$$ ($$$1\leq Q\leq 10^6$$$), the number of queries.
Each of the next $$$Q$$$ lines, contains an integer $$$1\leq a_k \leq 10^12$$$ the number of the octagone they want to know its distance to center of octagone 0.
Output $$$Q$$$ lines, where the $$$i$$$-th line contains a number indicating the distance between the center of octagone $$$a_i$$$ and the center of octagone $$$0$$$.
21100
4 200
The distance from the center of the octagone to the center of any of its sides, is 1.
