Fibonacci Suffix Search

Given the Fibonacci sequence \(F\) defined as:

\(F_0 = 0, \; F_1 = 1, \; F_m = F_{m-1} + F_{m-2}\) for \(m \ge 2\),

and a given digit string \(S\), find the smallest index \(k\) such that the decimal representation of \(F_k\) ends with \(S\). Note that the sequence indices start from 0.

Example:

• For \(S = 0\), since \(F_0 = 0\), the answer is 0.
• For \(S = 1\), \(F_1 = 1\) (and also \(F_2 = 1\)), the smallest valid index is 1.
• For \(S = 13\), \(F_7 = 13\) so the answer is 7.
• For \(S = 81\), \(F_19 = 4181\) which ends in 81, so the answer is 19.

inputFormat

The input consists of a single line containing a non-empty string \(S\) that represents a sequence of digits.

outputFormat

Output the smallest index \(k\) (0-indexed) such that the Fibonacci number \(F_k\) ends with the string \(S\).

sample

0

0