Counting Fibonacci Numbers

Time limit1sMemory limit256 MB

Summary

For each query pair a and b up to 10^100, count how many Fibonacci numbers fall in the closed interval [a, b].

Level: Medium5 of 10
Topics: Math, Binary search, String, Brute force
Solved: No attempts yet

Problem

The Fibonacci numbers are defined as follows.

$f_1 = 1$
$f_2 = 2$
$f_n = f_{n-1} + f_{n-2}$ (for $n \ge 3$ )

Given two integers $a$ and $b$ , write a program that counts how many Fibonacci numbers lie in the interval $[a, b]$ . In other words, count the Fibonacci numbers $f_i$ that satisfy $a \le f_i \le b$ .

Input

The input consists of several test cases. Each test case is a single line containing two non-negative integers $a$ and $b$ separated by a space ( $a \le b \le 10^{100}$ ). The two numbers are given without unnecessary leading zeros. The last line of the input contains two zeros, and this line is not processed.

Output

For each test case, print on its own line the number of Fibonacci numbers $f_i$ that satisfy $a \le f_i \le b$ .

Examples1

Example 1
Input
```
10 100
1234567890 9876543210
0 0
```
Expected output
```
5
4
```