Cơ số \(-2\). Số \(n\) được biểu diễn dưới dạng cơ số \(-2\) như sau:

\(n = b_0 + b_1(-2) + b_2(-2)^2 + b_3(-2)^3...+b_n(-2)^n\)

Lưu ý: \(b\) chỉ mang giá trị \(0\) hoặc \(1\)

Input

• Đầu vào sẽ bao gồm một nhiều dòng, mỗi dòng chứa một số dương nhỏ \(n\) \((-10^9 \le n \le 10^9)\).
• Nếu \(n=0\) có nghĩa là kết thúc bộ test

Output

• Với mỗi số được nhập vào, bạn phải in ra số \(n\) ở dạng cơ số \(-2\)

Example

Sample input

4
1
7
-2
0

Sample output

100
1
11011
10