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}$