Coco wants to make a chocolate bar in the shape of a triangle, composed of regular hexagonal pieces. Since making it plain is boring, she wants to create a pattern by joining two types of chocolate as shown in the figure below. White represents white chocolate, and blue represents mint chocolate.
The specific method for creating this pattern is as follows:
- The top vertex must have a mint chocolate.
- From the position of every mint chocolate, there must also be a mint chocolate at every position reachable by the following move:
- Move 1 unit in any direction where there is an adjacent chocolate, then turn 60 degrees to the left or right and move 1 more unit.
When the chocolates are numbered horizontally as shown in the figure, let's find the number of the $n$-th smallest mint chocolate.
Input
The first line contains the number of test cases $T$ ($1 \le T \le 10^5$).
Each of the following $T$ lines contains a single integer $n$ ($1 \le n \le 10^{16}$).
Output
For each test case, output the number of the $n$-th smallest mint chocolate on a single line.
Examples
Input 1
6 2 7 18 281 8284 59045
Output 1
5 20 52 841 24850 177133