“斐波那契”串

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

   通过一个学期的学习,哈士奇知道了斐波那契这种有趣的数列,这种数列由1,1开始,之后的斐波那契数就由之前的两数相加。用数学公式定义斐波那契数列可以看成如下形式:

    F( 1 ) = F( 2 ) = 1

    F( n ) = F( n - 1 ) + F( n - 2 )  ( n >= 3 )

    现在哈士奇定义了这样一种“斐波那契”串:

    11235813213455891442…

    不难看出这个串是这样构造的:

    将 F( 1 ) , F( 2 ),F(3)… 放入串中,产生的新串即“斐波那契”串。

    现在哈士奇想知道,“斐波那契”串的第 N 个数字是什么?你能编程解决这个问题吗?

Input

    输入包含一个正整数 N ( 1 <= N <= 100000)。

Output

    对于每个正整数 N ,输出“斐波那契”串中第 N 个数字。

Sample Input

8

Sample Output

3

Hint

Source

Miracle_QSH