Disjoint Fibonacci Sum Representations

This problem is based on the famous Fibonacci sequence defined as follows:

\( F_n = \begin{cases} 1 & (n \le 2)\\ F_{n-1}+F_{n-2} & (n \ge 3) \end{cases} \)

Each term is called a Fibonacci number. Given a positive integer n, we consider representations of n as a sum of some Fibonacci numbers. However, there is one twist: if you choose several representations (or schemes), then no Fibonacci number may appear in more than one representation. In other words, all chosen representations must be pairwise disjoint in terms of the Fibonacci numbers used.

Your task is to determine, for a given n, what is the maximum number of such disjoint representations (schemes) that you can form.

Note: In forming any single representation, each Fibonacci number can be used at most once.

inputFormat

The input consists of a single line containing a positive integer n (1 ≤ n ≤ 10⁹).

outputFormat

Output a single integer — the maximum number of disjoint representation schemes in which each scheme expresses n as the sum of distinct Fibonacci numbers.

sample

1

2