{"raw_statement":[{"iden":"statement","content":"我们定义满足如下条件的数对 $(x,y)$ 叫做奇妙数对：\n\n$k \\times \\gcd(x,y)=\\operatorname{lcm}(x,y)$ 并且 $P \\le \\gcd(x,y) \\le Q$（保证 $P \\le Q$）。\n\n有 $T$ 组数据，对于每一组数据，给定 $k,P,Q$ 三个数，求符合条件的数对 $(x,y)$ 的对数。\n\n**答案对 $10^9+7$ 取模。**"},{"iden":"input","content":"**本题有多组数据。**\n\n第一行一个整数 $T$，表示数据数量。\n\n接下来 $T$ 行，每行三个整数 $k,P,Q$。"},{"iden":"output","content":"对于每一组数据，给出对应答案，每组数据一行。\n\n"},{"iden":"note","content":"**注意并不寻常的时间限制。**\n\n对于 $100\\%$ 的数据 $1 \\le k \\le 10^{16}$，$1 \\le T \\le 50$，$1 \\le P \\le Q \\le 2\\times 10^9$。\n\n| 测试点 | $k$ | $T$ | $P$ | $Q$ | 总分 |\n| :----------: | :----------: | :----------: | :-------------: | :----------: | :----------: |\n| $1\\sim 3$ | $k \\le 3$ | $T=1$ | $P=1$ | $Q=1$ | $15$ |\n| $4\\sim 8$ | $k \\le 100$ | $T \\le 8$ | $P \\le 30$ |  $Q \\le 30$ |$15$ |\n| $9\\sim 13$ | $k \\le 10^3$ | $T \\le 50$ | $P \\le 500$ | $Q \\le 500$ | $25$ |\n| $14\\sim 18$ | $k \\le 10^{12}$ | $T \\le 50$ | $P \\le 10^4$ | $Q \\le 10^4$ | $15$ |\n| $19\\sim 22$ | $k \\le 10^{13}$ | $T \\le 50$ | $P \\le 10^6$ | $Q \\le 10^6$ | $12$ |\n| $23\\sim 28$ | $k \\le 10^{16}$ | $T \\le 50$ | $P \\le 2\\times10^9$ | $Q \\le 2\\times10^9$ | $18$ |\n\n**本题保证 $k$ 随机生成，并不存在极限卡人数据，时限已经开到 std 两倍，请各位选手放心。**"}],"translated_statement":null,"sample_group":[["5\n10 1 3\n30 1 5\n997 24 35\n34 39 99\n210 1000 1001","12\n40\n24\n244\n32"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}