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