Kilometers to Miles

While preparing for a half marathon (about 21 km), Sang-geun first ran 21 miles, then learned that the race is 21 kilometers rather than 21 miles, which is about 13 miles. Both 21 and 13 are Fibonacci numbers! Inspired by this, he devised a way to convert kilometers to miles using a Fibonacci numeral system.

The Fibonacci numbers are defined as follows.

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

Every positive integer $x$ can be written as a sum of distinct Fibonacci numbers. That is, there always exist an integer $k$ and $b_1, b_2, \ldots, b_k$ with $b_k = 1$ and $b_i \in \{0, 1\}$ ($1 \le i < k$) such that $x = \sum_{i=1}^{k} b_i \times F_i$. We write this representation as $b(x) = (b_k, b_{k-1}, \ldots, b_1)$. To make the representation unique, we require $b_i \times b_{i-1} = 0$ ($i > 1$); that is, no two 1s appear consecutively.

For example, 21 is $(1, 0, 0, 0, 0, 0, 0)$ and 13 is $(1, 0, 0, 0, 0, 0)$.

The kilometer value $x$ is converted to the mile value $y$ as follows.

1. Write $x$ in the Fibonacci numeral system as $b(x)$.
2. Shift $b(x)$ one bit to the right, discarding the last bit. Call the result $b(y)$.
3. Compute the value represented by $b(y)$; that value is $y$.

For example, 42 is $(1, 0, 0, 1, 0, 0, 0, 0)$ in the Fibonacci system. Shifting it one bit to the right gives $(1, 0, 0, 1, 0, 0, 0)$, whose value is $0 \times 1 + 0 \times 2 + 0 \times 3 + 1 \times 5 + 0 \times 8 + 0 \times 13 + 1 \times 21 = 26$.

Given kilometer values, write a program that converts each to miles using this algorithm.

The first line contains the number of kilometer values to convert, $t$. ($0 < t < 25000$)

Each of the next $t$ lines contains one kilometer value $x$ to convert. ($2 < x < 25000$)

For each kilometer value $x$, output the mile value $y$ obtained by the algorithm above, one per line.