斐波拉契数列

Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 91

Solved: 1

Description

斐波拉契数列（0, 1, 1, 2, 3, 5, 8, 13, 21….），其中第0项为0，第一项为1，现将其每一项都对10^13求余得到一个新的数字，给定一个数字x，求x为这个新数列中的第几项。

Input

输入包括多组数据，每组数据包括一行,每行包括一个整数x（其中0 <= x < 10^13）。

Output

每组数据输出一行，每行包括一个整数，代表所需的答案。

sample input

13
377

sample output

7
14

hint

source

Submit