Problem Description

We define a pair of numbers $(x,y)$ that satisfies the following conditions as a "wonderful number pair":

$k \times \gcd(x,y)=\operatorname{lcm}(x,y)$, and $P \le \gcd(x,y) \le Q$ (it is guaranteed that $P \le Q$).

There are $T$ test cases. For each test case, given three numbers $k,P,Q$, find the number of pairs $(x,y)$ that satisfy the conditions.

Output the answer modulo $10^9+7$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

The next $T$ lines each contain three integers $k,P,Q$.

Output Format

For each test case, output the corresponding answer, one per line.

5
10 1 3
30 1 5
997 24 35
34 39 99
210 1000 1001

12
40
24
244
32

Hint

Note that the time limit is not usual.

For $100\%$ of the testdata: $1 \le k \le 10^{16}$, $1 \le T \le 50$, $1 \le P \le Q \le 2\times 10^9$.

This problem guarantees that $k$ is generated randomly, and there is no extreme testdata intended to make it difficult. The time limit has already been set to twice that of the standard solution, so please feel assured.

Translated by ChatGPT 5