The Dual

0

0 votes
Very-Easy
Problem

“The Dual”, is to be played between Timo Ball and the KUKA. The KUKA understands only “0” and “1”. The KUKA can adjust its position by itself by default. There is an additional panel to train the KUKA. If you wish to train the KUKA, the usual rule is that it won’t begin with “0”. Moreover, two successive digits must not be both “1”. Hence, the KUKA won’t respond to Strings such as “11”. So the allowed instructions are 1, 10, 100, 101, 1000, 1001, . . . , 100010101010100010001. Each allowed instruction represents a positive integer in the order they appear (using length order, lexicographic order), that is,
1 : 1
2 : 10
3 : 100
4 : 101
5 : 1000 and so on..
Help KUKA by generating the allowed instruction code representations for integers given.

Input Format
The First line of each file contains a integer T denoting the number of test cases. The next T line contains an integer X each.

Output Format
For each integer X output print out the allowed instruction on a newline.

Constraints
1 ≤ T ≤ 105
2 ≤ X ≤ 108

Time Limit: 0.8
Memory Limit: 256
Source Limit:
Editor Image

?