Tổng ít nhất các số Fibonacci

Dãy Fibonacci với các số đầu tiên là:~1, 1, 2, 3, 5, 8, \ldots~ được định nghĩa bởi công thức sau: ~F_1 = 1, F_2 = 1, F_i = F_{i-1} + F_{i-2}~ với ~i > 2~.

Hãy biểu diễn một số tự nhiên ~N~ thành tổng của ít nhất các số Fibonacci khác nhau.

Input

Gồm một dòng duy nhất chứa số nguyên dương ~n~ thỏa ~1 \le N \le 2.10^{9}~.

Output

In ra biểu diễn số ~N~ thành tổng của ít nhất các số Fibonacci khác nhau.

Samples

10

10 = 8 + 2

129

129 = 89 + 34 + 5 + 1