Số Pinary là số nguyên chứa các chữ số 0 và 1 thoả mãn các điều kiện:

• Không bắt đầu bằng 0,
• Không chứa 2 số 1 liên tiếp nhau.

Ví dụ, các số sau là số Pinary: ~ 1, 10, 100, 101, 1000, 1001, 1010, . . .~ Còn các số sau không phải là Pinary: ~ 00101, 1001101 ~. Các số Pinary được sắp xếp theo thứ tự từ điển.

Yêu cầu: Cho số nguyên ~ n ~. Hãy xác định số Pinary thứ ~ n ~.

Dữ liệu vào

• Dòng đầu ghi số nguyên ~ k ~ ~ (1 ≤ k ≤ 50) ~ cho biết số lượng testcasce
• ~ k ~ dòng tiếp theo, mỗi dòng ghi một số nguyên ~ n ~ ~ (1 ≤ n ≤ 90000000) ~.

Kết quả

• Các số Pinary tìm được tương ứng với các số trong Input, mỗi số trên một dòng.

Ví dụ:

Input 1

3
7
2000
22 

Output 1

1010
1001000001001000
1000001