hackercupai/hackercup huggingface dataset:
Let's start with some notations and definitions. Let **m** be the fixed
positive integer.

1. Let **a** be an integer that coprime to **m**, that is, **gcd(a, m) = 1**. The minimal positive integer **k** such that **m** divides **ak − 1** is called the _multiplicative order of **a** modulo **m**_ and denoted as **ordm(a)**. For example, ** ord7(2) = 3** since **23 − 1 = 7** is divisible by **7** but **21 − 1** and **22 − 1** are not. It can be proven that **ordm(a)** exists for every **a** that coprime to **m**.
2. Denote by **L(m)** the maximal possible multiplicative order of some number modulo **m**. That is, **L(m) = max{ordm(a) : 1 ≤ a ≤ m, gcd(a, m)=1}**. For example,

**L(5) = max{ ord5(1), ord5(2), ord5(3), ord5(4)} = max{1, 4, 4, 2} = 4**

and

**L(6) = max{ord6(1), ord6(5)} = max{1, 2} = 2.**

3. Denote by **N(m)** the number of positive integers **a ≤ m** such that ** ordm(a) = L(m)**. For example, **N(5) = 2**, **N(6) = 1**, **N(8) = 3** (numbers that have maximal multiplicative order modulo **8** are **3, 5** and **7**).

Now your task is to find for the given positive integers **L** and **R** such
that **L ≤ R** the product

**N(L) ∙ N(L+1) ∙ ... ∙ N(R)**

modulo **109 \+ 7**.

### Input

The first line contains a positive integer **T**, the number of test cases.
**T** test cases follow. The only line of each test case contains two space
separated positive integers **L** and **R**.

### Output

For each of the test cases numbered in order from **1** to **T**, output "Case
#i: " followed by the value of required product modulo **109 \+ 7**.

### Constraints

**1 ≤ T ≤ 20
1 ≤ L ≤ R ≤ 1012
R − L ≤ 500000**