You are given three integers, namely L, R, and X, where X varies from \([L, R]\).

Write a program to find the sum of the number of ways in which X people are chosen. If you choose a \(person_i\) \((1 \le i \le X)\), then you cannot choose its neighboring person.

Input format

• First line: T (number of test cases)
• First line in each test case: Two space-separated integers L and R

Output format

For each test case, print the sum of the number of ways modulo \(10^9 + 7\) in which X people are chosen, where if you choose a \(person_i\) \((1 \le i \le X)\), you can choose one or none of its immediate neighbors, but not both.

Constraints

\(1 ≤ T ≤ 10^3\)
\(1 ≤ L ≤ R ≤ 10^9\)