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<=10^100. 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

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python

F = [1,1]
def fibo():
 for i in range(500):
  F.append(F[-2] + F[-1])

def main():
 fibo()
 #print len(str(F[-1]))
 #print len(str(10**100))
 while True:
  try:
   A, B = list(map(int, input().strip().split()[:2]))
   if A == 0 and B == 0: break
   print(len([x for x in F if x >= A and x <= B]))
  except:
   break

main()