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

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

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

그림처럼 가로 방향으로 번호를 매겼을 때, 번호가 $n$번째로 작은 민트 초콜릿의 번호를 구해 보자.

Input

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

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

Output

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

Examples

Input 1

6
2
7
18
281
8284
59045

Output 1

5
20
52
841
24850
177133