You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

斐波那契数列是非常出名的数列，它的公式是这样的:

1、 f[0] = 0;

2、 f[1] = 1;

3、 对于任意i>=2，都有f[i] = f[i-1] + f[i-2]。

于是，产生的斐波那契数列就是：0,1,1,2,3,5,8,13,21,34,...... 现在给出一个正整数N，你要找出一个最小的整数X，同时满足如下两个条件：

1、 X >= 0。

2、 N+X是斐波那契数列中的某一个数，或者N-X是斐波那契数列中的某一个数。

请输出满足条件的最小的X。

输入格式

一行，一个整数N。 1 <= N <= 1000000。

输出格式

一个满足条件的最小的X。

输入/输出例子1

输入：

15

输出：

2

输入/输出例子2

输入：

19

输出：

2

输入/输出例子3

输入：

8

输出：

0

样例解释

样例1

因为15-2=13，而13是斐波那契数列的其中一个数。

样例2

因为19+2=21，而21是斐波那契数列的其中一个数。

样例3

因为8本身已经是斐波那契数列的一个数了。