E. Jeopardized Projects
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eric has joined his district science fair with his engineering project The Palindromic Cereal Bridge. Envy is envious of Eric's unique project, so he decides to ruin it while Eric goes to talk with the CerealCodes team.

A project can be described by an array $$$a_1, a_2, \ldots, a_k$$$ of length $$$k$$$ consisting of positive integers. We call a project jeopardized if it is not palindromic  — that is, there is some $$$1 \le i \le k$$$ such that $$$a_i \neq a_{k - i + 1}$$$.

Envy likes the integers $$$l$$$ and $$$r$$$, and wants to know how many jeopardized projects there are satisfying the following: $$$$$$l \le \sum\limits_{i = 1}^{k}a_i \le r$$$$$$

Since the answer may be very large, output it modulo $$$1\,000\,000\,007$$$.

Please help him figure this out!

Input

The input consists of multiple tests. The first line contains $$$t$$$, the number of test cases ($$$1 \le t \le 2 \cdot 10^5$$$).

The only line of each test case contains $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^5$$$).

Output

For each test case, print the answer, modulo $$$1\,000\,000\,007$$$.

Example
Input
4
2 3
1 1
4 4
123 456
Output
2
0
4
318860857
Note

In the first test, there are $$$2$$$ jeopardized arrays:

  • $$$[1, 2]$$$
  • $$$[2, 1]$$$

In the second test, there are no jeopardized arrays.

In the third test, there are $$$4$$$ jeopardized arrays:

  • $$$[1, 1, 2]$$$
  • $$$[2, 1, 1]$$$
  • $$$[3, 1]$$$
  • $$$[1, 3]$$$

Problem Credits: Jesse Choe and Eric Hsu