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 \leq k \leq 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\ (0 < n \leq 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ụ: