킬로미터를 마일로

상근이는 하프 마라톤(약 21 km)을 준비하며 21마일을 뛰었다가, 마라톤 거리가 21마일이 아니라 21킬로미터이고 이는 약 13마일이라는 사실을 알게 되었다. 21과 13은 모두 피보나치 수다! 상근이는 여기서 착안해 피보나치 진법으로 킬로미터를 마일로 바꾸는 방법을 고안했다.

피보나치 수는 다음과 같이 정의한다.

• $F_1 = 1$
• $F_2 = 2$
• $F_{n+1} = F_n + F_{n-1}$ ($n > 1$)

모든 양의 정수 $x$는 서로 다른 피보나치 수들의 합으로 나타낼 수 있다. 즉, $b_k = 1$이고 $b_i \in {0, 1}$ ($1 \le i < k$)이면서 $x = \sum_{i=1}^{k} b_i \times F_i$를 만족하는 정수 $k$와 $b_1, b_2, \ldots, b_k$가 항상 존재한다. 이 표현을 $b(x) = (b_k, b_{k-1}, \ldots, b_1)$로 쓴다. 표현을 유일하게 만들기 위해 $b_i \times b_{i-1} = 0$ ($i > 1$)이라는 조건을 둔다. 즉, 1이 연속해서 나타나지 않는다.

예를 들어 21은 $(1, 0, 0, 0, 0, 0, 0)$으로, 13은 $(1, 0, 0, 0, 0, 0)$으로 나타낼 수 있다.

킬로미터 값 $x$를 마일 값 $y$로 바꾸는 방법은 다음과 같다.

1. $x$를 피보나치 진법 $b(x)$로 나타낸다.
2. $b(x)$를 오른쪽으로 한 비트 시프트한다. 이때 맨 마지막 비트는 버린다. 그 결과를 $b(y)$라고 한다.
3. $b(y)$가 나타내는 값을 계산하면 그 값이 $y$이다.

예를 들어 42는 피보나치 진법으로 $(1, 0, 0, 1, 0, 0, 0, 0)$이다. 이를 오른쪽으로 한 비트 시프트하면 $(1, 0, 0, 1, 0, 0, 0)$이 되고, 그 값은 $0 \times 1 + 0 \times 2 + 0 \times 3 + 1 \times 5 + 0 \times 8 + 0 \times 13 + 1 \times 21 = 26$이다.

킬로미터 값이 주어졌을 때, 이 알고리즘을 이용해 마일로 바꾸는 프로그램을 작성하시오.

첫째 줄에 마일로 바꿀 킬로미터 값의 개수 $t$가 주어진다. ($0 < t < 25000$)

다음 $t$개의 줄에 각각 마일로 바꿀 킬로미터 값 $x$가 주어진다. ($2 < x < 25000$)

각 킬로미터 값 $x$에 대해, 위 알고리즘으로 마일로 바꾼 값 $y$를 한 줄에 하나씩 출력한다.