题目描述

我们定义满足如下条件的数对 $(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$。

输出格式

对于每一组数据，给出对应答案，每组数据一行。

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

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$ 随机生成，并不存在极限卡人数据，时限已经开到 std 两倍，请各位选手放心。