「GMOI R1-T3」Number Pair
题目描述
我们定义满足如下条件的数对 $(x,y)$ 叫做奇妙数对：
$k \times \gcd(x,y)=\operatorname{lcm}(x,y)$ 并且 $P \le \gcd(x,y) \le Q$（保证 $P \le Q$）。
有 $T$ 组数据，对于每一组数据，给定 $k,P,Q$ 三个数，求符合条件的数对 $(x,y)$ 的对数。
**答案对 $10^9+7$ 取模。**
输入输出格式
输入格式
**本题有多组数据。**
第一行一个整数 $T$，表示数据数量。
接下来 $T$ 行，每行三个整数 $k,P,Q$。
输出格式
对于每一组数据，给出对应答案，每组数据一行。
输入输出样例
输入样例 #1
5
10 1 3
30 1 5
997 24 35
34 39 99
210 1000 1001输出样例 #1
12
40
24
244
32说明
**注意并不寻常的时间限制。**
对于 $100\%$ 的数据 $1 \le k \le 10^{16}$，$1 \le T \le 50$，$1 \le P \le Q \le 2\times 10^9$。
| 测试点 | $k$ | $T$ | $P$ | $Q$ | 总分 |
| :----------: | :----------: | :----------: | :-------------: | :----------: | :----------: |
| $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$ |
**本题保证 $k$ 随机生成，并不存在极限卡人数据，时限已经开到 std 两倍，请各位选手放心。**