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$