수학 게임

• Fibonacci Game에서 N이 더 커진 버전. Fibonacci Game에서는 첫턴에 최대 N-1개의 돌을 가져갈수 있었고, 그래서 이길수 없는 경우에는 -1을 출력하도록 되어있었지만, 여기에서는 최대 N개의 돌을 가져갈수 있기때문에 이길수 없는 경우는 생기지 않는다. 하지만 이길수 있는 경우에는 최소의 돌을 가져가는 방법만 출력하라고 되어있으므로, 결과적으로 출력해야 하는 값은 이길수 없을때 -1 대신 N을 출력한다는 것을 제외하고는 동일하다.
• 풀이는 Fibonacci Game과 동일.

"""Solution code for "BOJ 2862. 수학 게임".

- Problem link: https://www.acmicpc.net/problem/2862
- Solution link: http://www.teferi.net/ps/problems/boj/2862

Tags: [number theory]
"""


def zeckendorf_representation(n):
    ret = []
    a, b = 1, 1
    while b <= n:
        a, b = b, a + b
    while n:
        while a > n:
            a, b = b - a, a
        n -= a
        ret.append(a)
    return ret


def main():
    N = int(input())
    print(zeckendorf_representation(N)[-1])


if __name__ == '__main__':
    main()