Setting

You might remember the definition of the Fibonacci numbers (at this point in your study of computer science, you should have already dreamt of these at least once):

\( f_1 := 1 \)

\( f_2 := 2 \)

\( f_n := f_{n-1} + f_{n-2} \)

Given two numbers \(a\) and \(b\), calculate how many Fibonacci numbers there 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 \leq b \leq 10^{100}\).

Output

For each test case output on a single line the number of Fibonacci numbers \(f_i\) with \(a \leq f_i \leq b\).

Sample Input

10 100
1234567890 9876543210
0 0

Sample Output

5
4

This is challenge 10183 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (2 votes)
Average test runtime 0.25
Points (changes over time) 10
Tried by 10 users
Solved by 9 users

Global ranking

# Name Runtime Points worth
1 Pascal 0.14 15
2 Mac 0.15 14
3 ,s/java/NaN/gi 0.15 14
4 贝尔恩德 0.20 11
5 Justin 0.20 11
6 JB 0.26 8
7 Skøgland 0.32 7
8 AlexanderP 0.41 5
9 IeM 0.43 5