John Doe 有一个以 1013 为模的所有斐波那契数的列表。这个列表是无限的,以数字 0 和 1 开始。列表中的每个数字(除了前两个)都是前两个模 1013 的和。也就是说,John 的列表是根据斐波那契数列表中的每个数字替换为除以 1013 时的余数而得出的。
John 对数字 f (0 ≤ f < 1013) 感兴趣,现在想要找到它在上面给出的列表中的第一次出现。帮助 John 找到数字 f 在列表中第一次出现的数字,或者说明数字 f 在列表中没有出现。
约翰的列表中的编号从零开始。其中,第 0 个位置是数字 0,第 1 个位置是数字 1,第 2 个位置是数字 1,第 3 个位置是数字 2,第 4 个位置是数字 3,依此类推。因此,列表的开头如下所示:0, 1, 1, 2, 3, 5, 8, 13, 21, ...
输入
第一行包含单个整数 f (0 ≤ f < 1013) — 数字,我们应该在列表中找到哪个位置。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
输出
打印单个数字 — 给定数字在 John 的列表中第一次出现的数字。如果该数字没有出现在 John 的列表中,则打印 -1。
示例
输入 #1
13
输出 #1
7
输入 #2
377
输出 #2
14