You are given a set of binary elements. You have to eliminate the binary numbers that contain \(11\) as a substring. The resultant sequence will be 1, 10, 100, 101, 1000, and so on.

You are required to generate the code to determine the \(K^{th}\) value of the new sequence.

Input format

First line: \(T\) denoting the number of test cases
Next \(T\) lines: A single integer \(K\)

Output format

Print \(T\) lines representing the code to display the \(K^{th}\) value.

Constraints

\(1 \le T \le 10^{5}\)

\(1 \le K \le 10^{8}\)