题目描述

Fibonacci 是形如 $1,1,2,3,5,8,13,21,34,\cdots$ 这样的数字序列，我们可以看到，第一个两位数的 Fibonacci 数字是 $13$，也就是第 $7$ 个 Fibonacci 数字。那么，你能求出第一个 $n$ 位数字的 Fibonacci 数字是第几个数字吗？

输入格式

输入一个整数 $n,1\leq n\leq 1000$。

输出格式

输出第一个 $n$ 位数字的 Fibonacci 数字对应的序号。

样例

1

1

解释#1

第一个一位 Fibonacci 数字是 $1$，序号是 $1$。

2

7

解释#2

第一个两位的 Fibonacci 数字是 $13$，序号是 $7$。

3

12

解释#3

第一个三位的 Fibonacci 数字是 $144$，序号是 $12$。