 5

# Fibonacci Sum

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

#### The fibonacci relation is given by:

``````fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2), n >= 2, where fib(n) represents the nth fibonacci number.
``````
##### Input format:
``````The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, which denote the start and end of the range.
``````
##### Output format:
``````For each test case, print the sum of Fibonacci numbers between ‘fib(N)’ and ‘fib(M)’.

Print the output for each test case in a separate line.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 1000
0 <= N <= M <= 10^9

Where ‘T’ represents the number of test cases, and ‘N’ and ‘M’ represents the starting and ending of the range respectively.

Time Limit: 1 sec
``````
##### Sample Input 1:
``````2
2 6
0 5
``````
##### Sample Output 1:
``````19
12
``````
##### Explanation 1:
``````For the first test case,
The Fibonacci numbers between fib(2) and fib(6) are {1, 2, 3, 5, 8}. Their sum is equal to 19. Hence the output is 19.

For the second test case,
The Fibonacci numbers between fib(0) and fib(5) are {0, 1, 1, 2, 3, 5}. Their sum is equal to 12. Hence the output is 12.
``````
##### Sample Input 2:
``````2
3 6
6 7
``````
##### Sample Output 2:
``````18
21
``````   Console