Binary numbers
/

1-D Array, Arrays, Data Structures, String Manipulation

Problem
Editorial
Analytics

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

SAMPLE INPUT
2
3
9

SAMPLE OUTPUT
100
10001

Explanation

Test case 1: The sequence is 1,10,100 and so on . So the 3rd element of sequence is 100

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB