Hide

Problem H
Modified Gray Code

/problems/modifiedgraycode/file/statement/en/img-0001.jpg

The Gray Code is a well-known binary sequence in which successive elements differ by only one bit, and the bit chosen to be switched yields the smallest normal binary value not yet used. The first element of the sequence is the binary sequence corresponding to 0. For example, the 3-bit Gray Code sequence is 000, 001, 011, 010, 110, 111, 101, 100. So the element at index 0 is 000, the element at index 4 is 110, and so on.

We want to modify the Gray Code so that successive elements differ by an even number of bits, but again the bits selected to be changed should yield the smallest normal binary value not yet used. We call this the even Gray code. Here are the first 3 elements of the 5-bit even Gray Code:

0   0 0 0 0 0
1   0 0 0 1 1     (2 bits switched – positions 1 and 2)
2   0 0 1 0 1     (2 bits switched – positions 2 and 3)

Given an index $K$, give the element at index $K$ in the 10-bit even Gray Code.

Input

The first line of input consists of an integer $N$ ($1\le N\le 500$), which is the number of queries that will be made. The remaining $N$ lines each contains a positive integer $K$ ($1 \leq K \leq 500$) representing the index of the 10-bit even Gray Code.

Output

For each input query, print the 10-bit representation of the corresponding even Gray Code element. There may be leading 0’s but there should be no spaces between the digits.

Sample Input 1	Sample Output 1
1 2	0000000101

Sample Input 2	Sample Output 2
2 1 10	0000000011 0000010100

Problem HModified Gray Code

Input

Output

Problem H
Modified Gray Code