Problem F
Modified Gray Code

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.

1
2

0000000101

2
1
10

0000000011
0000010100