SỐ PINARY

Pinary là số nguyên chứa các 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 từ file văn bản PINARY.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên n (0<n≤90000000).

Kết quả: Đưa ra file văn bản PINARY.OUT các số Pinary tìm được, mỗi số trên một dòng.

Ví dụ:

PINARY.INP	PINARY.OUT
7 2000 22	1010 1001000001001000 1000001

SOLUTION - TEST - CODE