Colorful Chocolate

Coco wants to make chocolate shaped like regular hexagonal pieces joined together in triangles. Making plain chocolate would be dull, so she joins two kinds of chocolate to form a pattern. The white pieces are white chocolate, and the blue pieces are mint chocolate.

The pattern is built as follows.

• The top vertex must hold a mint chocolate.
• From every position holding mint chocolate, every point reachable by the following move must also hold mint chocolate.
  • Move one cell in any direction where an adjacent chocolate exists, then turn 60 degrees to the left or right and move one more cell.

Number each chocolate from top to bottom and from left to right, as shown in the picture. Find the number of the n-th smallest mint chocolate.

The first line contains the number of test cases $T$. ($1\le T\le 10^5$)

Each of the next $T$ lines contains one integer $n$. ($1\le n\le 10^{16}$)

For each test case, print on one line the number of the n-th smallest mint chocolate.