P8926 "GMOI R1-T3" Number Pair

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$.**

**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$.

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

**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$. | Test Point | $k$ | $T$ | $P$ | $Q$ | Total Score | | :----------: | :----------: | :----------: | :-------------: | :----------: | :----------: | | $1\sim 3$ | $k \le 3$ | $T=1$ | $P=1$ | $Q=1$ | $15$ | | $4\sim 8$ | $k \le 100$ | $T \le 8$ | $P \le 30$ | $Q \le 30$ |$15$ | | $9\sim 13$ | $k \le 10^3$ | $T \le 50$ | $P \le 500$ | $Q \le 500$ | $25$ | | $14\sim 18$ | $k \le 10^{12}$ | $T \le 50$ | $P \le 10^4$ | $Q \le 10^4$ | $15$ | | $19\sim 22$ | $k \le 10^{13}$ | $T \le 50$ | $P \le 10^6$ | $Q \le 10^6$ | $12$ | | $23\sim 28$ | $k \le 10^{16}$ | $T \le 50$ | $P \le 2\times10^9$ | $Q \le 2\times10^9$ | $18$ | **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