알록달록 초콜릿 만들기

코코는 정육각형 초콜릿이 삼각형 모양으로 서로 붙어 있는 초콜릿을 만들려고 한다. 그냥 만들면 재미가 없으니, 아래 그림처럼 두 종류의 초콜릿을 붙여서 무늬를 만들려고 한다. 흰색은 화이트 초콜릿이고, 파란색은 민트 초콜릿이다.

이 무늬를 만드는 방법은 다음과 같다.

• 맨 위 꼭짓점에는 민트 초콜릿이 놓여 있어야 한다.
• 민트 초콜릿이 놓인 모든 위치에서, 다음과 같이 이동할 수 있는 모든 지점에도 민트 초콜릿이 놓여 있어야 한다.
  • 이웃한 초콜릿이 있는 방향 중 아무 방향으로 1칸 이동한 뒤, 왼쪽 또는 오른쪽으로 60도 돌아서 1칸 더 이동한다.

각 초콜릿에 위에서 아래로, 왼쪽에서 오른쪽으로 그림처럼 번호를 매겼을 때, 번호가 $n$번째로 작은 민트 초콜릿의 번호를 구해 보자.

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. ($1\le T\le 10^5$)

다음 $T$개의 줄 각각에는 정수 $n$이 하나씩 주어진다. ($1\le n\le 10^{16}$)

각 테스트 케이스에 대해, 번호가 $n$번째로 작은 민트 초콜릿의 번호를 한 줄에 출력한다.