28257번 - 알록달록 초콜릿 만들기

문제

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

이 무늬를 만드는 구체적인 방법은 다음과 같다.

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

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

입력

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

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

출력

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

제한

힌트