Magical Pairs Count

We define a pair of positive integers \((x,y)\) to be a magical pair if they satisfy the following conditions:

\[ k \times \gcd(x,y) = \operatorname{lcm}(x,y) \quad \text{and} \quad P \le \gcd(x,y) \le Q \]

It can be shown that if we write \(x = d\,a\) and \(y = d\,b\) with \(d = \gcd(x,y)\) and \(\gcd(a,b)=1\), then \(\operatorname{lcm}(x,y)=d\,a\,b\). The equation becomes:

\[ k \times d = d \times a\,b \quad \Longrightarrow \quad a\,b = k \]

Thus the problem reduces to the following: for a given integer \(k\), let \(f(k)\) be the number of pairs \((a,b)\) of positive integers satisfying \(a\,b=k\) and \(\gcd(a,b)=1\). It is known that if \(k\) has \(r\) distinct prime factors then \(f(k)=2^r\) (with the convention \(2^0=1\) when \(k=1\)).

For each test case, given integers \(k\), \(P\), and \(Q\) (with the guarantee \(P \le Q\)), there are exactly \(Q-P+1\) choices for \(d=\gcd(x,y)\) (since \(d\) can be any integer in the interval \([P,Q]\)), and for each such \(d\) there are \(f(k)\) corresponding pairs \((a,b)\). Therefore, the total number of magical pairs is:

\[ \text{Answer} = (Q-P+1) \times 2^r \quad (\text{mod } 10^9+7) \]

Given \(T\) test cases, output the answer for each test case on a new line.

inputFormat

The first line contains an integer \(T\) \((1 \le T \le \text{some limit})\) representing the number of test cases. Each of the following \(T\) lines contains three integers \(k\), \(P\), and \(Q\) separated by spaces.

\(k\): the integer used in the equation,

\(P\) and \(Q\): the lower and upper bounds for \(\gcd(x,y)\) respectively (with \(P \le Q\)).

outputFormat

For each test case, output a single integer: the number of magical pairs \((x,y)\) satisfying the given conditions, taken modulo \(10^9+7\). Each answer should be on its own line.

sample

3
1 1 10
6 2 5
12 3 7

10
16
20