DCP - Fun With Fibonacci


The Fibonacci sequence is a set of numbers that starts with a zero, followed by a one, and proceeds based on the rule that, each number (called a Fibonacci number) is equal to the sum of the previous two numbers. If the Fibonacci sequence is denoted F(n), where n is the term in the sequence,

Fibonacci series

Now your task is to find the total number of odd Fibonacci numbers and total number of even Fibonacci numbers between a range (consider 0 as an even number).

Input

First Line of the input contains T, representing the number of test case (1 <= T <= 50). For each test case contains two integers N and M where (1 <= N <= 1018) and (1 <= M <= 1018).

Output

You have to calculate total number of odd Fibonacci numbers and total number of even Fibonacci numbers between Nth Fibonacci number and Mth Fibonacci number.

For each test case print case number with the desire answer as show sample output.

Example

Input:
2
2 6
1 5

Output:
Case 1:
Odd = 4
Even = 1
Case 2:
Odd = 3
Even = 2

hide comments
David: 2022-02-22 06:01:37

@nadstratosfer While it seems strange to say "between the 9th and 4th fibonacci", it means the same grammatically as "between the 4th and 9th fibonacci". Just swap.
While the problem does not say inclusive, the problem means inclusive.
In addition, many problems at SPOJ say f(0) = 0, this problem does not specify. To get AC, f(1) = 0, f(2) = 1, etc.
First Java solution!

Last edit: 2022-02-22 06:04:07
nadstratosfer: 2021-11-11 04:09:46

Input features L > R, what does judge expect for such cases? Outputting Odd = 0, Even = 0 gives WA.

Please remove language restrictions.

Last edit: 2021-11-12 04:07:23

Added by:Sifat
Date:2021-09-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG GO JAVA JULIA PYTHON PYPY3 PYTHON3