TFIB - How many Fibs

no tags 

Recall the definition of the Fibonacci numbers:

f1 := 1
f2 := 2
fn := fn-1 + fn-2 (n>=3)

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].

Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a=b=0. Otherwise, a<=b<=10100. The numbers a and b are given with no superfluous leading zeros.

Output

For each test case output on a single line the number of Fibonacci numbers fi with a<=fi<=b.

Example

Input:
10 100
1234567890 9876543210
0 0

Output:
5
4

hide comments
Suraj Lal Gupta: 2014-10-24 09:42:36

My program passes sample input but getting 'Wrong Answer' through the judge. Can anybody help me find the issue? <snip>

Last edit: 2023-05-09 17:09:07
V Sriharsha: 2013-06-30 18:15:27

Silly mistake corrected

Last edit: 2013-06-30 18:40:14
Julian Leyh: 2012-02-10 09:44:56

@Saurabh: which other coding platform? maybe their time measuring is broken, or they use different input for the judging.

Saurabh Jain: 2012-01-30 19:07:49

solved this problem on another coding platform and got AC with time =0.00 sec but when i am submitting the same sol. here , i get TLE!!! why is it so??

Adrian Kuegel: 2010-05-25 15:14:35

@Alexandre: Your precalculated Fibonacci numbers are wrong!

Last edit: 2010-05-25 15:15:13
alexandre ignjatovic: 2010-05-21 09:54:09

My prog seems to pass the sample input, but it won't make it through the judge. Is there some tricky test case i can not imagine ?


Added by:Adrian Kuegel
Date:2005-07-05
Time limit:2.723s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:University of Ulm Local Contest 2000